Submission #295265

#	Time	Username	Problem	Language	Result	Execution time	Memory
295265		williamMBDK	Toy Train (IOI17_train)	C++11	0 / 100	896 ms	3520 KiB

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;
			good[c] = !good[c];
			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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 11
• Subtask 4: 0 / 11
• Subtask 5: 0 / 12
• Subtask 6: 0 / 51