oj.uz

Submission #593793

# Submission time Handle Problem Language Result Execution time Memory
593793 2022-07-11T15:26:36 Z FatihSolak Toy Train (IOI17_train) C++17
11 / 100
 2000 ms 197432 KB 
#include "train.h"
#include <bits/stdc++.h>
#define N 5005
using namespace std;
int path[N][N];
int path2[N][N];
bool special[N];
vector<int> adj[N];
vector<int> adj2[N];
void dfs(int v,int num){
	path[num][v] = 1;
	for(auto u:adj[v]){
		if(!path[num][u]){
			dfs(u,num);
		}
	}
}
void dfs2(int v,int num){
	path2[num][v] = 1;
	for(auto u:adj2[v]){
		if(!path2[num][u]){
			dfs2(u,num);
		}
	}
}
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
	int n = a.size();
	int m = u.size();
	for(int i=0;i<m;i++){
		adj[u[i]].push_back(v[i]);
		if(!r[v[i]])
			adj2[u[i]].push_back(v[i]);
	}
	for(int i = 0;i<n;i++){
		dfs(i,i);
		dfs2(i,i);
	}
	for(int i = 0;i<n;i++){
		if(!r[i]){
			for(auto u:adj[i]){
				if(path2[u][i] && !r[u]){
					special[i] = 1;
				}
			}
		}
	}
	vector<int> res(n);
	for(int i = 0; i < n; i++){
		res[i] = 1;
		for(int j = 0;j<n;j++){
			if(special[j] && path[i][j]){
				res[i] = 0;
			}
		}
	}
	return res;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 273 ms 88160 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 596 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 359 ms 182392 KB Output is correct
2 Correct 340 ms 165452 KB Output is correct
3 Correct 323 ms 146324 KB Output is correct
4 Incorrect 1630 ms 196960 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
5 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 738 ms 120272 KB Output is correct
2 Correct 365 ms 196940 KB Output is correct
3 Correct 556 ms 195440 KB Output is correct
4 Correct 632 ms 176740 KB Output is correct
5 Correct 840 ms 197088 KB Output is correct
6 Correct 725 ms 196452 KB Output is correct
7 Correct 755 ms 195820 KB Output is correct
8 Correct 561 ms 191492 KB Output is correct
9 Correct 105 ms 105984 KB Output is correct
10 Correct 968 ms 148612 KB Output is correct
11 Correct 945 ms 127988 KB Output is correct
12 Correct 951 ms 154452 KB Output is correct
13 Correct 1143 ms 197432 KB Output is correct
14 Correct 707 ms 197108 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2068 ms 197224 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

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