답안 #295259

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
295259 2020-09-09T14:47:39 Z williamMBDK 장난감 기차 (IOI17_train) C++11
11 / 100
878 ms 3960 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;
}
# 결과 실행 시간 메모리 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 -
# 결과 실행 시간 메모리 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 -
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 Grader output
1 Incorrect 179 ms 2808 KB 3rd lines differ - on the 696th token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 63 ms 3320 KB 3rd lines differ - on the 2nd token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 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 -