Submission #64839

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
64839	2018-08-05T19:58:18 Z	mohammad_kilani	Toy Train (IOI17_train)	C++17	11 / 100	407 ms	1964 KB

train

#include "train.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 5010;
vector< int > res , a , g[N] , r , g2[N];
int n , vis[N] , vi = 0 , last , out[N];
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[g2[node][i]] == a[node]){
			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]){
				if(out[g2[node][i]] == 0){
					res[g2[node][i]] = a[node];
					make(g2[node][i]);
				}
			}
			else{
				res[g2[node][i]] = a[node] ^ 1;
				make(g2[node][i]);
			}
		}
	}
}

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

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

bool DFS2(int node){
	if(res[node] != -1 || have[node]) 
		return false;
	if(node == last)
		return true;
	vis[node] = vi;
	for(int i=0;i<g[node].size();i++){
		if(vis[g[node][i]] != vi && DFS2(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<n;i++)
		have[i] = r[i];
	for(int i = 0;i<(int)u.size();i++){
		g[u[i]].push_back(v[i]);
		g2[v[i]].push_back(u[i]);
	}
	for(int i=0;i<n;i++){
		if(res[i] != -1) continue;
		last = i;
		vi++;
		if(a[i] == 0 || r[i]){
			for(int j = 0;j<g[i].size();j++){
				if(a[g[i][j]] == a[i] && vis[g[i][j]] != vi && DFS(g[i][j])){
					res[i] = a[i];
					break;
				}
			}
		}
		if(res[i] != -1)
			make(i);

	}
	for(int i=0;i<n;i++){
		if(a[i] == 1){
			vi++;
			have[i] = DFS3(i);
		}
	}
	for(int i=0;i<n;i++){
		if(res[i] == -1 && a[i] == 0){
			vi++;
			last = i;
			if(DFS2(i)){
				res[i] = 0;
				make(i);
			}
		}
	}
	for(int i=0;i<n;i++){
		if(res[i] == -1 && a[i] == 0){
			res[i] = a[i] ^ 1;
			make(i);
		}
	}
	for(int i=0;i<n;i++)
		if(res[i] == -1)
			res[i] = a[i] ^ 1;
	return res;
}

Compilation message

train.cpp: In function 'void make(int)':
train.cpp:11: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:47:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[node].size();i++){
              ~^~~~~~~~~~~~~~~
train.cpp: In function 'bool DFS3(int)':
train.cpp:62:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[node].size();i++){
              ~^~~~~~~~~~~~~~~
train.cpp: In function 'bool DFS2(int)':
train.cpp:75: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:99: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	13 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 2nd token, expected: '1', found: '0'
2	Halted	0 ms	0 KB	-

Subtask #3
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	1716 KB	Output is correct
2	Correct	52 ms	1784 KB	Output is correct
3	Correct	106 ms	1820 KB	Output is correct
4	Correct	14 ms	1820 KB	Output is correct
5	Correct	45 ms	1820 KB	Output is correct
6	Correct	266 ms	1820 KB	Output is correct
7	Correct	21 ms	1820 KB	Output is correct
8	Correct	184 ms	1820 KB	Output is correct
9	Correct	407 ms	1820 KB	Output is correct
10	Correct	73 ms	1832 KB	Output is correct
11	Correct	106 ms	1832 KB	Output is correct
12	Correct	39 ms	1832 KB	Output is correct
13	Correct	19 ms	1836 KB	Output is correct
14	Correct	16 ms	1836 KB	Output is correct
15	Correct	17 ms	1836 KB	Output is correct
16	Correct	15 ms	1964 KB	Output is correct
17	Correct	15 ms	1964 KB	Output is correct
18	Correct	277 ms	1964 KB	Output is correct