Submission #65146

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
65146	2018-08-06T18:21:02 Z	mohammad_kilani	Toy Train (IOI17_train)	C++17	11 / 100	296 ms	2072 KB

train

#include "train.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 5010;
vector< int > res , a , r , g[N] , g2[N];
int n , out[N] , out2[N] , last , vis[N] , vi;
bool have[N];

void make(int node){
	for(int i=0;i<g2[node].size();i++){
		if(res[g2[node][i]] != -1)
			continue;
		out[g2[node][i]]--;
		if(a[node] == a[g2[node][i]]){
			if(res[node] == a[node]){
				res[g2[node][i]] = a[node];
				make(g2[node][i]);
			}
			else{
				if(out[g2[node][i]] == 0){
					res[g2[node][i]] = a[node] ^ 1;
					make(g2[node][i]);
				}
			}
		}
		else{
			if(res[node] != a[node]){
				res[g2[node][i]] = a[node] ^ 1;
				make(g2[node][i]);
			}
			else{
				if(out[g2[node][i]] == 0){
					res[g2[node][i]] = a[node];
					make(g2[node][i]);
				}
			}
		}
	}
}

void make2(int node){
	for(int i=0;i<g2[node].size();i++){
		if(have[g2[node][i]]) continue;
		out2[g2[node][i]]--;
		if(out2[g2[node][i]] == 0){
			have[g2[node][i]] = true;
			make2(g2[node][i]);
			continue;
		}
		if(a[g2[node][i]] == 1){
			have[g2[node][i]] = true;
			make2(g2[node][i]);
		}
	}
}

bool DFS(int node){
	if(a[node] == 0)
		return (res[node] == 1);
	if(node == last)
		return true;
	vis[node] = vi;
	for(int i=0;i<g[node].size();i++){
		if(vis[g[node][i]] != vi && DFS(g[node][i]))
			return true;
	}
	return false;
}


std::vector<int> who_wins(std::vector<int> A, std::vector<int> R, std::vector<int> u, std::vector<int> v) {
	a = A;
	n = (int)a.size();
	r = R;
	res.resize(n , -1);
	for(int i = 0;i<(int)u.size();i++){
		g[u[i]].push_back(v[i]);
		g2[v[i]].push_back(u[i]);
		out[u[i]]++;
		out2[u[i]]++;
	}
	for(int i=0;i<n;i++){
		if(have[i]) continue;
		have[i] = r[i];
		if(have[i])
			make2(i);
	}
	for(int i=0;i<n;i++){
		if(res[i] != -1) continue;
		if(a[i] == 0 && out2[i] > 0){
			res[i] = 0;
			make(i);
		}
	}
	for(int i=0;i<n;i++){
		if(res[i] != -1 && a[i] == 0){
			res[i] = 1;
			make(i);
		}
	}
	for(int i=0;i<n;i++){
		if(res[i] != -1) continue;
		last = i;
		vi++;
		if(r[i]){
			for(int j = 0;j<g[i].size();j++){
				if(vis[g[i][j]] != vi && DFS(g[i][j])){
					res[i] = 1;
					break;
				}
			}
			if(res[i] != -1)			
				make(i);
		}
	}
	for(int i=0;i<n;i++){
		if(res[i] == -1)
			res[i] = 0;
	}
	return res;
}

Compilation message

train.cpp: In function 'void make(int)':
train.cpp:10:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g2[node].size();i++){
              ~^~~~~~~~~~~~~~~~
train.cpp: In function 'void make2(int)':
train.cpp:42:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g2[node].size();i++){
              ~^~~~~~~~~~~~~~~~
train.cpp: In function 'bool DFS(int)':
train.cpp:63:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[node].size();i++){
              ~^~~~~~~~~~~~~~~
train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:106:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0;j<g[i].size();j++){
                  ~^~~~~~~~~~~~

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	9 ms	1144 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	3 ms	1144 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	20 ms	1824 KB	Output is correct
2	Correct	48 ms	1868 KB	Output is correct
3	Correct	121 ms	1868 KB	Output is correct
4	Correct	16 ms	1868 KB	Output is correct
5	Correct	22 ms	1868 KB	Output is correct
6	Correct	129 ms	1868 KB	Output is correct
7	Correct	15 ms	1868 KB	Output is correct
8	Correct	13 ms	1868 KB	Output is correct
9	Correct	17 ms	1868 KB	Output is correct
10	Correct	14 ms	1868 KB	Output is correct
11	Correct	19 ms	1868 KB	Output is correct
12	Correct	17 ms	1868 KB	Output is correct
13	Correct	20 ms	1948 KB	Output is correct
14	Correct	15 ms	1964 KB	Output is correct
15	Correct	16 ms	2072 KB	Output is correct
16	Correct	15 ms	2072 KB	Output is correct
17	Correct	16 ms	2072 KB	Output is correct
18	Correct	296 ms	2072 KB	Output is correct