Submission #584712

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
584712	2022-06-27T21:28:36 Z	1ne	Toy Train (IOI17_train)	C++14	0 / 100	460 ms	1548 KB

train

#include "train.h"
#include<bits/stdc++.h>
using namespace std;
std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
	int n = (int)a.size();
	int m = (int)u.size();
	vector<int>ans(n,0);
	vector<vector<int>>adj(n);
	for (int i = 0;i<m;++i){
		adj[u[i]].push_back(v[i]);
	}
	vector<int>visited(n,0);
	vector<int>cnt(n,0);
	vector<int>parent(n,-1);
	function<int(int)>dfs = [&](int u){
		if (visited[u] ==  2)return cnt[u];
		visited[u] = 1;
		int ans = 0;
		for (auto x:adj[u]){
			if (visited[x] == 1){
				int y = u;
				vector<int>temp;
				int got = r[x];
				temp.push_back(x);
				while(y!=x){
					got|=r[y];
					temp.push_back(y);
					y = parent[y];
				}
				ans |= got;
				for (auto y:temp)cnt[y]|=got;
			}
			else{
				int temp = parent[x];
				parent[x] = u;
				ans|=dfs(x);
				parent[x] = temp;
			}
		}
		visited[u] = 2;
		return cnt[u] = (ans | cnt[u]);
	};	
	for (int i = 0;i<n;++i){
		if (visited[i] == 2){
			ans[i] = cnt[i];
		}
		else{
			ans[i] = dfs(i);
		}
	}
	for (int j = 0;j<n;++j){
		for (int i = 0;i<m;++i){
				cnt[u[i]]|=cnt[v[i]];
		}
	}
	for (int i = 0;i<n;++i){
		ans[i]|=cnt[i];
	}
	for (int i = 0;i<n;++i){
		visited[i] = false;
	}
	for (int i = 0;i<n;++i){
		if (visited[i] == 2){
			ans[i] = cnt[i];
		}
		else{
			ans[i] = dfs(i);
		}
	}
	return ans;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	99 ms	1516 KB	3rd lines differ - on the 1st token, expected: '0', found: '1'
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	212 KB	3rd lines differ - on the 8th token, expected: '0', found: '1'
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	252 ms	1492 KB	Output is correct
2	Correct	281 ms	1412 KB	Output is correct
3	Correct	292 ms	1384 KB	Output is correct
4	Correct	383 ms	1484 KB	Output is correct
5	Correct	263 ms	1380 KB	Output is correct
6	Correct	290 ms	1152 KB	Output is correct
7	Correct	275 ms	1084 KB	Output is correct
8	Correct	238 ms	1120 KB	Output is correct
9	Correct	262 ms	1144 KB	Output is correct
10	Correct	280 ms	1072 KB	Output is correct
11	Correct	266 ms	1036 KB	Output is correct
12	Correct	262 ms	1012 KB	Output is correct
13	Correct	460 ms	1548 KB	Output is correct
14	Incorrect	438 ms	1476 KB	3rd lines differ - on the 1st token, expected: '1', found: '0'
15	Halted	0 ms	0 KB	-