oj.uz

Submission #795470

# Submission time Handle Problem Language Result Execution time Memory
795470 2023-07-27T10:11:46 Z fatemetmhr Toy Train (IOI17_train) C++17
11 / 100
 95 ms 24908 KB 
//  ~ Be Name Khoda ~  //
 
#include "train.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")
 
using namespace std;
 
typedef long long ll;
 
#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
 
const int maxn  =  1e6   + 10;
const int maxn5 =  5e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   + 7;
const ll  inf   =  1e18;
 
int cnt[maxn5], q[maxn5], cntkeep[maxn5];
vector <int> adj[maxn5], jda[maxn5], ret;
bool mark[maxn5], good[maxn5], keep[maxn5];
int n, m;
 
std::vector<int> who_wins(std::vector<int> a, std::vector<int> ch, std::vector<int> u, std::vector<int> v) {
	n = a.size(); 
	m = u.size();
 	for(int i = 0; i < m; i++){
 		adj[u[i]].pb(v[i]);
 		jda[v[i]].pb(u[i]);
 		cnt[u[i]]++;
 	}
 	while(true){
	 	int x = -1;
		for(int i = 0; i < n; i++){
			keep[i] = good[i];
			cntkeep[i] = cnt[i];
		}
		for(int i = 0; i < n; i++) if(!good[i] && !ch[i])
			x = i;
		if(x == -1)
			break;
	 	int l = 0, r = 0;
	 	for(auto u : jda[x]) if(!good[u] && !ch[u]){
	 		if(!a[u]){
	 			q[r++] = u;
	 			good[u] = true;
	 		}
	 		else if(cnt[u] > 1)
	 			cnt[u]--;
	 		else{
	 			q[r++] = u;
	 			good[u] = true;
	 		}
	 	}
	 	while(l < r){
	 		int v = q[l++];
		 	for(auto u : jda[v]) if(!good[u] && !ch[u]){
		 		if(!a[u]){
		 			q[r++] = u;
		 			good[u] = true;
		 		}
		 		else if(cnt[u] > 1)
		 			cnt[u]--;
		 		else{
		 			q[r++] = u;
		 			good[u] = true;
		 		}
		 	}
	 	}
	 	if(!good[x]){
	 		ch[x] = true;
	 		for(int i = 0; i < n; i++){
	 			good[i] = keep[i];
	 			cnt[i] = cntkeep[i];
	 		}
	 	}
	 	else{
	 		int l = 0, r = 0;
	 		for(int i = 0; i < n; i++) if(good[i])
	 			q[r++] = i;
		 	while(l < r){
		 		int v = q[l++];
			 	for(auto u : jda[v]) if(!good[u]){
			 		if(!a[u]){
			 			q[r++] = u;
			 			good[u] = true;
			 		}
			 		else if(cnt[u] > 1)
			 			cnt[u]--;
			 		else{
			 			q[r++] = u;
			 			good[u] = true;
			 		}
			 	}
		 	}
	 	}
 	}

	for(int i = 0; i < n; i++)
		ret.pb(!good[i]);
 	return ret;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23804 KB Output is correct
2 Correct 12 ms 23800 KB Output is correct
3 Correct 10 ms 23804 KB Output is correct
4 Incorrect 12 ms 23696 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
5 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 24788 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 21 ms 24660 KB Output is correct
2 Correct 64 ms 24756 KB Output is correct
3 Correct 38 ms 24832 KB Output is correct
4 Correct 23 ms 24840 KB Output is correct
5 Correct 62 ms 24868 KB Output is correct
6 Correct 95 ms 24844 KB Output is correct
7 Correct 85 ms 24816 KB Output is correct
8 Correct 37 ms 24788 KB Output is correct
9 Correct 23 ms 24788 KB Output is correct
10 Correct 24 ms 24836 KB Output is correct
11 Correct 23 ms 24864 KB Output is correct
12 Correct 24 ms 24880 KB Output is correct
13 Correct 72 ms 24908 KB Output is correct
14 Correct 78 ms 24788 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 24840 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 28 ms 24404 KB 3rd lines differ - on the 14th token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -