oj.uz

Submission #33692

# Submission time Handle Problem Language Result Execution time Memory
33692 2017-10-31T17:59:41 Z mohammad_kilani Toy Train (IOI17_train) C++14
11 / 100
 2000 ms 2952 KB 
#include <bits/stdc++.h>
#include "train.h"
using namespace std;
const int N = 5010;
bool win[N];
int vis[N];
int vi = 0;
vector<int> g[N];
vector<int> r;
bool DFS(int node,int source){
	if(vis[node] == vi) return false;
	if(r[node]) return false;
	vis[node] = vi;
	if(node == source) return true;
	for(int i=0;i<g[node].size();i++){
		if(DFS(g[node][i],source)) return true;
	}
	return false;
}

bool DFS2(int node){
	if(win[node]) return true;
	if(vis[node] == vi) return false;
	vis[node] = vi;
	for(int i=0;i<g[node].size();i++){
		if(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) {
	vector<int> ans;
	r = R;
	int n = a.size();
	for(int i=0;i<u.size();i++) g[u[i]].push_back(v[i]);
	for(int i=0;i<n;i++){
		for(int j=0;j<g[i].size();j++){
			vi++;
			if(DFS(g[i][j],i)) win[i] = 1;
		}
	}
	for(int i=0;i<n;i++){
		vi++;
		if(DFS2(i)) win[i] = 1;
		ans.push_back(win[i] ^ 1);
	}
	return ans;
}

Compilation message

train.cpp: In function 'bool DFS(int, int)':
train.cpp:15: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:25: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:35:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<u.size();i++) g[u[i]].push_back(v[i]);
               ^
train.cpp:37:16: 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 0 ms 2572 KB 3rd lines differ - on the 14th token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2160 KB 3rd lines differ - on the 2nd token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1193 ms 2952 KB Output is correct
2 Correct 649 ms 2940 KB Output is correct
3 Correct 173 ms 2936 KB Output is correct
4 Execution timed out 2000 ms 2928 KB Execution timed out
5 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1169 ms 2772 KB Output is correct
2 Correct 386 ms 2740 KB Output is correct
3 Correct 606 ms 2928 KB Output is correct
4 Correct 136 ms 2916 KB Output is correct
5 Correct 1189 ms 2916 KB Output is correct
6 Correct 1343 ms 2904 KB Output is correct
7 Correct 1153 ms 2900 KB Output is correct
8 Correct 419 ms 2756 KB Output is correct
9 Correct 23 ms 2744 KB Output is correct
10 Correct 1643 ms 2928 KB Output is correct
11 Correct 1773 ms 2928 KB Output is correct
12 Correct 1649 ms 2928 KB Output is correct
13 Correct 1686 ms 2928 KB Output is correct
14 Correct 746 ms 2748 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 2780 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2572 KB 3rd lines differ - on the 14th token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -