Submission #295259

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
295259	2020-09-09T14:47:39 Z	williamMBDK	Toy Train (IOI17_train)	C++11	11 / 100	878 ms	3960 KB

train

#include<bits/stdc++.h>
using namespace std;
#include "train.h"
int N, M;
vector<vector<int>> adj, rev;
vector<int> res, rescomps;
vector<int> owns, charging;
vector<int> component;
vector<int> good;
vector<vector<int>> componentADJ;
int dfs(int node){
	if(rescomps[node] != -1) return rescomps[node];
	rescomps[node] = good[node];
	for(auto comp : componentADJ[node]){
		if(dfs(comp)){
			rescomps[node] = 1;
		}
	}
	return rescomps[node];
}
vector<bool> bfs(vector<vector<int>>& adj, int s){
	vector<bool> res (N);
	queue<int> q;
	q.push(s);
	//cout << "bfs" << endl;
	while(!q.empty()){
		auto curr = q.front(); q.pop();
		if(res[curr]) continue;
		res[curr] = 1;
		//cout << curr << endl;
		for(auto e : adj[curr]){
			//cout << e << " ";
			q.push(e);
		}
		//cout << endl;
	}
	//cout << "end bfs" << endl;
	return res;
}
std::vector<int> who_wins(std::vector<int> ta, std::vector<int> tr, std::vector<int> tu, std::vector<int> tv) {
	N = ta.size();
	M = tu.size();
	adj = vector<vector<int>> (N);
	rev = vector<vector<int>> (N);
	res = vector<int> (N, -1);
	component = vector<int> (N, -1);
	good = vector<int> (N);
	owns = ta;
	charging = tr;
	map<int,map<int,bool>> edges;
	// cout <<"start" << endl;
	for(int i = 0; i < M; i++) {
	       	adj[tu[i]].push_back(tv[i]); 
	       	rev[tv[i]].push_back(tu[i]); 
		//  cout << tv[i] << " "  << tu[i] << endl;
		edges[tv[i]][tu[i]] = 1;
	}
	int c = -1;
	for(int i = 0; i < N; i++){
		if(component[i] == -1){
			c++;
			vector<bool> seen1 = bfs(adj, i);
			vector<bool> seen2 = bfs(rev, i);
			int cnt = 0;
			bool isgood = 0;
			// cout << "component" << endl;
			for(int i = 0; i < N; i++){
				// cout << seen1[i] << " " << seen2[i] << endl;
				if(seen1[i] && seen2[i]){
					component[i] = c;
					// cout << i << endl;
					cnt++;
					if(charging[i]) isgood = 1;
				}
			}
			if(cnt == 1) good[c] = (isgood && edges[i][i]);
			else good[c] = isgood;
			componentADJ.push_back({});
		}
	}
	c++;
	rescomps = vector<int> (c, -1);
	for(int i = 0; i < M; i++){
		componentADJ[component[tu[i]]].push_back(component[tv[i]]);
	}
	for(int i = 0; i < N; i++){
		dfs(component[i]);
		res[i] = rescomps[component[i]];
	}
	return res;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	675 ms	2680 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	256 KB	3rd lines differ - on the 8th token, expected: '0', found: '1'
2	Halted	0 ms	0 KB	-

Subtask #3
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	878 ms	3660 KB	Output is correct
2	Correct	760 ms	3960 KB	Output is correct
3	Correct	661 ms	3704 KB	Output is correct
4	Correct	100 ms	3320 KB	Output is correct
5	Correct	210 ms	3576 KB	Output is correct
6	Correct	285 ms	3320 KB	Output is correct
7	Correct	75 ms	3192 KB	Output is correct
8	Correct	30 ms	3200 KB	Output is correct
9	Correct	27 ms	3072 KB	Output is correct
10	Correct	64 ms	3304 KB	Output is correct
11	Correct	122 ms	3064 KB	Output is correct
12	Correct	97 ms	3252 KB	Output is correct
13	Correct	38 ms	3320 KB	Output is correct
14	Correct	43 ms	3320 KB	Output is correct
15	Correct	40 ms	3320 KB	Output is correct
16	Correct	47 ms	3284 KB	Output is correct
17	Correct	47 ms	3320 KB	Output is correct
18	Correct	693 ms	2808 KB	Output is correct