oj.uz

Submission #990362

# Submission time Handle Problem Language Result Execution time Memory
990362 2024-05-30T10:10:07 Z StefanSebez Toy Train (IOI17_train) C++14
16 / 100
 1160 ms 1876 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];
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);
	}
}
std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
	std::vector<int> res(a.size());
	int n=a.size(),m=u.size();
	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){

	}
	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 1140 KB Output is correct
5 Correct 3 ms 1116 KB Output is correct
6 Correct 3 ms 1116 KB Output is correct
7 Correct 3 ms 1116 KB Output is correct
8 Correct 2 ms 1116 KB Output is correct
9 Correct 3 ms 1116 KB Output is correct
10 Correct 3 ms 1024 KB Output is correct
11 Correct 2 ms 1116 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 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 184 ms 1624 KB Output is correct
2 Correct 220 ms 1636 KB Output is correct
3 Correct 254 ms 1628 KB Output is correct
4 Correct 1160 ms 1552 KB Output is correct
5 Correct 688 ms 1536 KB Output is correct
6 Correct 480 ms 1508 KB Output is correct
7 Correct 812 ms 1368 KB Output is correct
8 Correct 270 ms 1372 KB Output is correct
9 Correct 253 ms 1372 KB Output is correct
10 Correct 331 ms 1456 KB Output is correct
11 Correct 292 ms 1372 KB Output is correct
12 Correct 59 ms 1372 KB Output is correct
13 Correct 729 ms 1764 KB Output is correct
14 Correct 704 ms 1780 KB Output is correct
15 Correct 743 ms 1876 KB Output is correct
16 Correct 760 ms 1768 KB Output is correct
17 Correct 735 ms 1760 KB Output is correct
18 Correct 502 ms 1412 KB Output is correct

Subtask #4
0 / 11.0

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

Subtask #5
0 / 12.0

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