oj.uz

Submission #1025771

# Submission time Handle Problem Language Result Execution time Memory
1025771 2024-07-17T09:50:02 Z amirhoseinfar1385 Toy Train (IOI17_train) C++17
16 / 100
 939 ms 1368 KB 
#include "train.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=5000+10;
vector<int>adj[maxn];
int n,shar[maxn],arez[maxn],m,dp[maxn],vas[maxn],dide[maxn];

int dfs(int u){
	if(shar[u]||arez[u]){
		return 0;
	}
	if(dide[u]==2){
		return 0;
	}
	if(dide[u]==1){
		return 1;
	}
	dide[u]=1;
	int ret=0;
	for(auto x:adj[u]){
		ret|=dfs(x);
	}
	dide[u]=2;
	return ret;
}

bool ber(int u){
	for(int i=0;i<n;i++){
		vas[i]=dide[i]=0;
	}
	return 1^dfs(u);
}

std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
	n=(int)a.size();
	m=(int)u.size();
	for(int i=0;i<=n;i++){
		adj[i].clear();
		shar[i]=vas[i]=dide[i]=dp[i]=arez[i]=0;
	}
	for(int i=0;i<n;i++){
		if(a[i]){
			arez[i]=1;
		}
		if(r[i]){
			shar[i]=1;
		}
	}
	for(int i=0;i<m;i++){
		adj[u[i]].push_back(v[i]);
	}
	for(int i=0;i<n;i++){
		dp[i]=ber(i);
	}
	for(int asd=0;asd<=n;asd++){
		for(int i=0;i<n;i++){
			int cnt=0;
			int f=0;
			for(auto x:adj[i]){
				if(x==i){
					f=1;
					continue;
				}
				if(dp[x]==1){
					cnt++;
				}
			}
			if(arez[i]){
				if(f){
					if(shar[i]==0&&cnt==0){
						dp[i]=0;
					}
				}else{
					if(cnt==0){
						dp[i]=0;
					}
				}
			}else{
				if(f){
					if(shar[i]==0||cnt!=(int)adj[i].size()-1){
						dp[i]=0;
					}
				}else{
					if(cnt!=(int)adj[i].size()){
						dp[i]=0;
					}
				}
			}
		}
	}
	vector<int>res(n);
	for(int i=0;i<n;i++){
		res[i]=dp[i];
	}
	return res;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 980 KB Output is correct
2 Correct 113 ms 860 KB Output is correct
3 Correct 105 ms 1064 KB Output is correct
4 Correct 106 ms 856 KB Output is correct
5 Correct 157 ms 1064 KB Output is correct
6 Correct 121 ms 856 KB Output is correct
7 Correct 94 ms 860 KB Output is correct
8 Correct 79 ms 1068 KB Output is correct
9 Correct 125 ms 856 KB Output is correct
10 Correct 114 ms 1036 KB Output is correct
11 Correct 68 ms 1012 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

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

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 1116 KB Output is correct
2 Correct 301 ms 1176 KB Output is correct
3 Correct 355 ms 1116 KB Output is correct
4 Correct 256 ms 1116 KB Output is correct
5 Correct 563 ms 1364 KB Output is correct
6 Correct 390 ms 1112 KB Output is correct
7 Correct 414 ms 1360 KB Output is correct
8 Correct 292 ms 1224 KB Output is correct
9 Correct 193 ms 1184 KB Output is correct
10 Correct 197 ms 1112 KB Output is correct
11 Correct 187 ms 1116 KB Output is correct
12 Correct 190 ms 1116 KB Output is correct
13 Correct 939 ms 1316 KB Output is correct
14 Correct 493 ms 1368 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 885 ms 1296 KB Output is correct
2 Correct 174 ms 1112 KB Output is correct
3 Correct 414 ms 1252 KB Output is correct
4 Correct 140 ms 1368 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Incorrect 99 ms 860 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
7 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 980 KB Output is correct
2 Correct 113 ms 860 KB Output is correct
3 Correct 105 ms 1064 KB Output is correct
4 Correct 106 ms 856 KB Output is correct
5 Correct 157 ms 1064 KB Output is correct
6 Correct 121 ms 856 KB Output is correct
7 Correct 94 ms 860 KB Output is correct
8 Correct 79 ms 1068 KB Output is correct
9 Correct 125 ms 856 KB Output is correct
10 Correct 114 ms 1036 KB Output is correct
11 Correct 68 ms 1012 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Incorrect 0 ms 348 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
14 Halted 0 ms 0 KB -