鱼不要过来啊！

NC206697. 鱼不要过来啊！

描述

一天，有一条鱼想找DD玩，但是DD不想见它，因为DD觉得鱼就是个憨憨！

他们住在一个奇怪的宿舍里，这个宿舍有n个房间，他们共度过m秒。

从第1秒到第m秒中每一秒会出现一扇门，并且在下一秒会消失，第i秒的门出现在第 $a_i$ 号房间，通往第 $b_i$ 号房间(单向)，它只允许鱼通过或者只允许DD通过。

对于每一秒钟，如果所在的房间如果出现了一扇允许自己通过的门，那么可以选择是否通过该门，通过一扇门不消耗任何时间。

初始鱼在第1号房间，DD在第x号房间。
DD知道每一秒会出现什么样的门，知道初始鱼在1号房间，但不知道鱼会怎么行动。

DD想知道如果初始他在第x个房间，是否存在一个方案使得无论鱼怎么行动他都可以始终不和鱼见面。

对于x从1到n你都需要输出答案。

注意如果初始在同一房间那么也算见面。

鱼来啦！！！快跑啊！！！

输入描述

第一行两个数字n,m表示n个房间，共m秒。
接下来m行每行三个数字。
表示该门只允许鱼通过
表示该门只允许DD通过
,

输出描述

一行n个数，之间用空格隔开
第i个数为1表示初始在第i号房间可以始终不和鱼见面，0表示不可以。

示例1

输入:

输出:

0 1 1 1

说明:

除了一开始就见面，其他情况DD有门就走便能逃过一劫！

示例2

输入:

输出:

0 1 1 0

说明:

初始DD在2号或者3号，那么可以去3号房躲着。
初始DD在4号，那么第3秒去2号房是危险的，因为里面可能有鱼！而最后鱼也可能去4号房！所以是不安全的！

上次编辑到这里，代码来自缓存点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 32ms, 内存消耗: 2040K, 提交时间: 2020-07-22 15:23:12

#include <cstdio>

using namespace std;

const int max_n = 1e5 + 5;

int n, m, t[max_n], a[max_n], b[max_n], T[max_n];

signed main() {
//    freopen("in", "r", stdin), freopen("out", "w", stdout);
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++)scanf("%d %d %d", &t[i], &a[i], &b[i]);
    for (int i = 2; i <= n; i++)T[i] = -1;
    for (int i = 1; i <= m; i++)if (t[i] == 1 && T[a[i]] != -1 && T[b[i]] == -1)T[b[i]] = i;
    for (int i = m; i >= 1; i--)if (t[i] == 2 && T[a[i]] != -1 && T[b[i]] == -1 && T[a[i]] > i)T[a[i]] = -1;
    for (int i = 1; i <= n; i++)printf("%d ", T[i] == -1 ? 1 : 0);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 59ms, 内存消耗: 2268K, 提交时间: 2020-06-28 19:48:10

#include<bits/stdc++.h>
using namespace std;

int t[100005],a[100005],b[100005],T[100005]={0};
int main()
{
	int i,n,m;
	scanf("%d%d",&n,&m);
	for(i=2;i<=n;i++)T[i]=1e9;
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&t[i],&a[i],&b[i]);
		if(t[i]==1&&T[a[i]]!=1e9&&T[b[i]]==1e9)T[b[i]]=i;
	}
	for(i=m;i>=1;i--)if(t[i]==2&&T[b[i]]==1e9&&T[a[i]]>i)T[a[i]]=1e9;
	for(i=1;i<=n;i++)printf("%d ",T[i]==1e9?1:0);
}