oj.uz

Submission #295252

# Submission time Handle Problem Language Result Execution time Memory
295252 2020-09-09T14:43:21 Z williamMBDK Toy Train (IOI17_train) C++14
0 / 100
 908 ms 3760 KB 
#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 737 ms 2692 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 908 ms 3760 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 203 ms 2808 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 79 ms 3320 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 737 ms 2692 KB secret mismatch
2 Halted 0 ms 0 KB -