oj.uz

답안 #1025769

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1025769 2024-07-17T09:49:06 Z amirhoseinfar1385 장난감 기차 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -