oj.uz

Submission #790121

# Submission time Handle Problem Language Result Execution time Memory
790121 2023-07-22T10:48:58 Z fatemetmhr Toy Train (IOI17_train) C++17
5 / 100
 26 ms 24460 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++){
		if(u[i] == v[i])
			loop[u[i]] = true;
		else
			mark[v[i]] = true;
	}
	vector <int> ans;
	for(int j = 0; j < n; j++){
		bool re = r[n - 1];
		for(int i = j; i < n; i++) if(loop[i]){
			if(r[i] && a[i]){
				re = true;
				break;
			}
			if(!r[i] && !a[i]){
				re = false;
				break;
			}
			if(i + 1 < n && !mark[i + 1]){
				re = r[i];
				break;
			}
		}
		ans.pb(re);
	}
	return ans;
	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;
	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 = false;
		for(int j = 0; j < n; j++) if(good[j] && mark[j])
			re = true;
		ans.pb(re);
	}
	return ans;

}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 24148 KB Output is correct
2 Correct 14 ms 24044 KB Output is correct
3 Correct 14 ms 24004 KB Output is correct
4 Correct 14 ms 24080 KB Output is correct
5 Correct 15 ms 24072 KB Output is correct
6 Correct 15 ms 24080 KB Output is correct
7 Correct 14 ms 24064 KB Output is correct
8 Correct 14 ms 24148 KB Output is correct
9 Correct 15 ms 24068 KB Output is correct
10 Correct 15 ms 24100 KB Output is correct
11 Correct 21 ms 24080 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 23804 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 22 ms 24364 KB Output is correct
2 Correct 26 ms 24432 KB Output is correct
3 Correct 22 ms 24404 KB Output is correct
4 Incorrect 23 ms 24444 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
5 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 24276 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 23 ms 24460 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 15 ms 24148 KB Output is correct
2 Correct 14 ms 24044 KB Output is correct
3 Correct 14 ms 24004 KB Output is correct
4 Correct 14 ms 24080 KB Output is correct
5 Correct 15 ms 24072 KB Output is correct
6 Correct 15 ms 24080 KB Output is correct
7 Correct 14 ms 24064 KB Output is correct
8 Correct 14 ms 24148 KB Output is correct
9 Correct 15 ms 24068 KB Output is correct
10 Correct 15 ms 24100 KB Output is correct
11 Correct 21 ms 24080 KB Output is correct
12 Incorrect 13 ms 23804 KB 3rd lines differ - on the 2nd token, expected: '1', found: '0'
13 Halted 0 ms 0 KB -