oj.uz

Submission #390049

# Submission time Handle Problem Language Result Execution time Memory
390049 2021-04-15T06:40:44 Z Keshi Toy Train (IOI17_train) C++17
22 / 100
 1633 ms 135944 KB 
//In the name of God
#include <bits/stdc++.h>
#include "train.h"
using namespace std;

typedef int ll;
typedef pair<ll, ll> pll;

const ll maxn = 5100;
const ll mod = 1e9 + 7;
const ll inf = 1e9;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()

ll n, m, c[maxn], t;
bool del[maxn], ok[maxn], vis[maxn], w[maxn], okk[maxn];
bool sub1 = 1, sub3 = 1, sub4 = 1;
vector<ll> vec, g[maxn], gp[maxn], com[maxn];
bitset<maxn> can[maxn];

void dfs(ll p, ll v){
	vis[v] = 1;
	if(del[v]) return;
	for(ll u : g[v]){
		can[p][u] = 1;
		if(!vis[u]) dfs(p, u);
	}
	vec.pb(v);
}
bool solve(ll v){
	if(w[v]) return 1;
	vis[v] = 1;
	for(ll u : g[v]){
		if(!vis[u] && solve(u)) return 1;
	}
	return 0;
}

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> v, vector<int> u){
	n = Sz(a);
	m = Sz(v);
	for(ll i = 0; i < m; i++){
		if(u[i] != v[i] && u[i] != v[i] + 1) sub1 = 0;
		g[v[i]].pb(u[i]);
		gp[u[i]].pb(v[i]);
	}
	vector<int> res(n);
	for(ll i = 0; i < n; i++){
		if(a[i]) sub4 = 0;
		else sub3 = 0;
	}
	for(ll i = 0; i < n; i++){
		if(sub3) ok[i] = r[i];
		else ok[i] = r[i] ^ 1;
		if(sub4) del[i] = r[i];
	}
	for(ll i = 0; i < n; i++){
		fill(vis, vis + n + 1, 0);
		dfs(i, i);
	}
	for(ll i = 0; i < n; i++){
		if(del[i]) continue;
		for(ll j = 0; j < n; j++){
			if(ok[j] && can[i][j] && can[j][i]) w[i] = 1;
		}
	}
	for(ll i = 0; i < n; i++){
		fill(vis, vis + n, 0);
		res[i] = solve(i);
		if(sub4) res[i] ^= 1;
	}
	return res;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 539 ms 69804 KB Output is correct
2 Correct 590 ms 69732 KB Output is correct
3 Correct 698 ms 69704 KB Output is correct
4 Correct 1628 ms 135336 KB Output is correct
5 Correct 1263 ms 135944 KB Output is correct
6 Correct 1317 ms 69344 KB Output is correct
7 Correct 805 ms 69352 KB Output is correct
8 Correct 602 ms 70144 KB Output is correct
9 Correct 736 ms 70544 KB Output is correct
10 Correct 626 ms 69868 KB Output is correct
11 Correct 629 ms 37584 KB Output is correct
12 Correct 105 ms 8496 KB Output is correct
13 Correct 1624 ms 135388 KB Output is correct
14 Correct 1608 ms 135404 KB Output is correct
15 Correct 1633 ms 135596 KB Output is correct
16 Correct 1592 ms 135512 KB Output is correct
17 Correct 1607 ms 135308 KB Output is correct
18 Correct 1055 ms 69396 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 836 ms 2460 KB Output is correct
2 Correct 299 ms 20624 KB Output is correct
3 Correct 310 ms 19972 KB Output is correct
4 Correct 138 ms 8388 KB Output is correct
5 Correct 742 ms 70576 KB Output is correct
6 Correct 687 ms 36344 KB Output is correct
7 Correct 691 ms 36744 KB Output is correct
8 Correct 272 ms 20632 KB Output is correct
9 Correct 48 ms 2520 KB Output is correct
10 Correct 1094 ms 4548 KB Output is correct
11 Correct 1040 ms 3356 KB Output is correct
12 Correct 1057 ms 4804 KB Output is correct
13 Correct 888 ms 69752 KB Output is correct
14 Correct 563 ms 36540 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 51.0

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