oj.uz

Submission #790125

# Submission time Handle Problem Language Result Execution time Memory
790125 2023-07-22T10:50:15 Z fatemetmhr Toy Train (IOI17_train) C++17
11 / 100
 1070 ms 25672 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], cmp[maxn5];
int num = 0;
vector <int> adj[maxn5], jda[maxn5], ver;
bool mark[maxn5], loop[maxn5], good[maxn5], rem[maxn5];
 
void dfs1(int v){
	mark[v] = true;
	for(auto u : adj[v]) if(!mark[u] && !rem[u])
		dfs1(u);
	ver.pb(v);
}
 
void dfs2(int v){
	mark[v] = true;
	cmp[v] = num;
	cnt[num]++;
	for(auto u : jda[v]) if(!mark[u] && !rem[u])
		dfs2(u);
 
}
 
std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
	int 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]);
		if(u[i] == v[i])
			loop[u[i]] = true;
	}
	for(int i = 0; i < n; i++) if(r[i])
		rem[i] = true;
 
	for(int i = 0; i < n; i++) if(!mark[i] && !rem[i])
		dfs1(i);
	reverse(all(ver));
	memset(mark, false, sizeof mark);
	for(auto u : ver) if(!mark[u] && !rem[u]){
		dfs2(u);
		num++;
	}
	for(int i = 0; i < n; i++) if(!rem[i] && (loop[i] || cnt[cmp[i]] > 1))
		good[i] = true;
	vector <int> ans;
	for(int i = 0; i < n; i++) if(r[i])
		rem[i] = false;
	for(int i = 0; i < n; i++){
		memset(mark, false, sizeof mark);
		ver.clear();
		dfs1(i);
		bool re = true;
		for(int j = 0; j < n; j++) if(good[j] && mark[j])
			re = false;
		ans.pb(re);
	}
	return ans;
 
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 292 ms 25200 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 Incorrect 12 ms 24228 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 234 ms 25560 KB Output is correct
2 Correct 239 ms 25608 KB Output is correct
3 Correct 234 ms 25440 KB Output is correct
4 Incorrect 1070 ms 25416 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 797 ms 25172 KB Output is correct
2 Correct 205 ms 25284 KB Output is correct
3 Correct 373 ms 25416 KB Output is correct
4 Correct 551 ms 25400 KB Output is correct
5 Correct 426 ms 25428 KB Output is correct
6 Correct 380 ms 25672 KB Output is correct
7 Correct 412 ms 25428 KB Output is correct
8 Correct 392 ms 25484 KB Output is correct
9 Correct 95 ms 25256 KB Output is correct
10 Correct 1004 ms 25616 KB Output is correct
11 Correct 952 ms 25580 KB Output is correct
12 Correct 996 ms 25616 KB Output is correct
13 Correct 586 ms 25472 KB Output is correct
14 Correct 350 ms 25352 KB Output is correct

Subtask #5
0 / 12.0

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