oj.uz

Submission #1025769

# Submission time Handle Problem Language Result Execution time Memory
1025769 2024-07-17T09:49:06 Z amirhoseinfar1385 Toy Train (IOI17_train) C++17
11 / 100
 1416 ms 1552 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]){
		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
0 / 5.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 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 249 ms 1440 KB Output is correct
2 Correct 242 ms 1552 KB Output is correct
3 Correct 223 ms 1472 KB Output is correct
4 Incorrect 779 ms 1508 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 199 ms 1108 KB Output is correct
2 Correct 311 ms 1112 KB Output is correct
3 Correct 352 ms 1116 KB Output is correct
4 Correct 263 ms 1244 KB Output is correct
5 Correct 573 ms 1112 KB Output is correct
6 Correct 402 ms 1240 KB Output is correct
7 Correct 494 ms 1212 KB Output is correct
8 Correct 307 ms 1192 KB Output is correct
9 Correct 241 ms 1116 KB Output is correct
10 Correct 227 ms 1116 KB Output is correct
11 Correct 201 ms 1232 KB Output is correct
12 Correct 197 ms 1248 KB Output is correct
13 Correct 989 ms 1296 KB Output is correct
14 Correct 515 ms 1116 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 51.0

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