Submission #584711

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
584711	2022-06-27T21:27:05 Z	1ne	Toy Train (IOI17_train)	C++14	0 / 100	358 ms	1672 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;
	};	
	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];
	}
	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	0 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	291 ms	1492 KB	Output is correct
2	Correct	295 ms	1404 KB	Output is correct
3	Correct	293 ms	1484 KB	Output is correct
4	Correct	336 ms	1612 KB	Output is correct
5	Correct	293 ms	1384 KB	Output is correct
6	Correct	289 ms	1164 KB	Output is correct
7	Correct	294 ms	980 KB	Output is correct
8	Correct	293 ms	1108 KB	Output is correct
9	Correct	259 ms	1140 KB	Output is correct
10	Correct	268 ms	1100 KB	Output is correct
11	Correct	266 ms	980 KB	Output is correct
12	Correct	251 ms	1008 KB	Output is correct
13	Correct	351 ms	1672 KB	Output is correct
14	Incorrect	358 ms	1536 KB	3rd lines differ - on the 1st token, expected: '1', found: '0'
15	Halted	0 ms	0 KB	-