oj.uz

Submission #990367

# Submission time Handle Problem Language Result Execution time Memory
990367 2024-05-30T10:18:57 Z StefanSebez Toy Train (IOI17_train) C++14
16 / 100
 1062 ms 1652 KB 
#include "train.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
const int N=5050;
vector<int>E[N],E1[N];
vector<int>r;
bool task3was[N],task3was1[N];
void task3DFS(int u){
	task3was[u]=true;
	for(auto i:E[u]){
		if(!task3was[i]) task3DFS(i);
	}
}
void task3DFS1(int u){
	task3was1[u]=true;
	for(auto i:E1[u]){
		if(!task3was1[i]) task3DFS1(i);
	}
}
bool task4was[N],task4was1[N];
void task4DFS(int u){
	task4was[u]=true;
	for(auto i:E[u]){
		if(!task4was[i] && r[i]==0) task4DFS(i);
	}
}
void task4DFS1(int u){
	task4was1[u]=true;
	for(auto i:E1[u]){
		if(!task4was1[i] && r[i]==0) task4DFS1(i);
	}
}
void task4DFS2(int u){
	task4was[u]=true;
	for(auto i:E[u]){
		if(!task4was[i]) task4DFS(i);
	}
}
std::vector<int> who_wins(std::vector<int> a, std::vector<int> rtemp, std::vector<int> u, std::vector<int> v) {
	std::vector<int> res(a.size());
	int n=a.size(),m=u.size();
	r=rtemp;
	for(int i=0;i<m;i++){
		E[u[i]].pb(v[i]);
		E1[v[i]].pb(u[i]);
	}
	bool subtask1=true;
	for(int i=0;i<m;i++) if(v[i]!=u[i] && v[i]!=u[i]+1) subtask1=false;
	bool subtask3=true;
	for(int i=0;i<n;i++) if(a[i]==0) subtask3=false;
	bool subtask4=true;
	for(int i=0;i<n;i++) if(a[i]==1) subtask4=false;
	if(subtask1){
		for(int i=0;i<n;i++){
			for(int j=i;j<n;){
				bool bul=false,bul2=false;
				for(auto k:E[j]){
					if(k==j+1) bul=true;
					if(k==j) bul2=true;
				}
				//printf("%i: %i %i\n",j,bul2,bul);
				if(a[j]==1){
					if(bul2 && r[j]==1) {res[i]=1;break;}
					else if(bul) j++;
					else {res[i]=0;break;}
				}
				else{
					if(bul2 && r[j]==0) {res[i]=0;break;}
					else if(bul) j++;
					else {res[i]=1;break;}
				}
			}
		}
	}
	else if(subtask3){
		bool ima[N]={false};
		for(int i=0;i<n;i++){
			if(r[i]==0) continue;
			task3DFS(i);
			task3DFS1(i);
			for(int j=0;j<n;j++){
				if(j!=i && task3was[j] && task3was1[j]) ima[i]=true;
				task3was[j]=task3was1[j]=false;
			}
			for(auto j:E[i]){
				if(j==i) ima[i]=true;
			}
		}
		for(int i=0;i<n;i++){
			task3DFS(i);
			res[i]=0;
			for(int j=0;j<n;j++){
				if(task3was[j] && ima[j]) res[i]=1;
				task3was[j]=task3was1[j]=false;
			}
		}
	}
	else if(subtask4){
		bool ima[N]={false};
		for(int i=0;i<n;i++){
			if(r[i]==1) continue;
			task4DFS(i);
			task4DFS1(i);
			for(int j=0;j<n;j++){
				if(j!=i && task4was[j] && task4was1[j]) ima[i]=true;
				task4was[j]=task4was1[j]=false;
			}
			for(auto j:E[i]){
				if(j==i) ima[i]=true;
			}
		}
		for(int i=0;i<n;i++){
			task4DFS2(i);
			res[i]=1;
			for(int j=0;j<n;j++){
				if(task4was[j] && ima[j]) res[i]=0;
				task4was[j]=task4was1[j]=false;
			}
		}
	}
	return res;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1116 KB Output is correct
2 Correct 3 ms 1116 KB Output is correct
3 Correct 3 ms 1116 KB Output is correct
4 Correct 3 ms 1024 KB Output is correct
5 Correct 4 ms 1116 KB Output is correct
6 Correct 3 ms 1116 KB Output is correct
7 Correct 2 ms 1116 KB Output is correct
8 Correct 2 ms 1116 KB Output is correct
9 Correct 2 ms 1116 KB Output is correct
10 Correct 2 ms 1116 KB Output is correct
11 Correct 2 ms 1112 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 1652 KB Output is correct
2 Correct 217 ms 1624 KB Output is correct
3 Correct 255 ms 1632 KB Output is correct
4 Correct 1062 ms 1372 KB Output is correct
5 Correct 587 ms 1372 KB Output is correct
6 Correct 473 ms 1532 KB Output is correct
7 Correct 765 ms 1372 KB Output is correct
8 Correct 254 ms 1368 KB Output is correct
9 Correct 260 ms 1368 KB Output is correct
10 Correct 318 ms 1620 KB Output is correct
11 Correct 273 ms 1368 KB Output is correct
12 Correct 60 ms 1372 KB Output is correct
13 Correct 737 ms 1372 KB Output is correct
14 Correct 714 ms 1588 KB Output is correct
15 Correct 724 ms 1372 KB Output is correct
16 Correct 723 ms 1584 KB Output is correct
17 Correct 721 ms 1596 KB Output is correct
18 Correct 485 ms 1112 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 1372 KB Output is correct
2 Incorrect 301 ms 1368 KB 3rd lines differ - on the 48th token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1368 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 Correct 3 ms 1116 KB Output is correct
2 Correct 3 ms 1116 KB Output is correct
3 Correct 3 ms 1116 KB Output is correct
4 Correct 3 ms 1024 KB Output is correct
5 Correct 4 ms 1116 KB Output is correct
6 Correct 3 ms 1116 KB Output is correct
7 Correct 2 ms 1116 KB Output is correct
8 Correct 2 ms 1116 KB Output is correct
9 Correct 2 ms 1116 KB Output is correct
10 Correct 2 ms 1116 KB Output is correct
11 Correct 2 ms 1112 KB Output is correct
12 Incorrect 0 ms 600 KB 3rd lines differ - on the 2nd token, expected: '1', found: '0'
13 Halted 0 ms 0 KB -