oj.uz

Submission #390051

# Submission time Handle Problem Language Result Execution time Memory
390051 2021-04-15T06:47:23 Z Keshi Toy Train (IOI17_train) C++17
22 / 100
 1641 ms 136044 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> solve1(vector<int> a, vector<int> r, vector<int> v, vector<int> u){
	ll n = Sz(a);
	ll m = Sz(v);
	for(ll i = 0; i < m; i++){
		g[v[i]].pb(u[i]);
	}
	vector<int> res(n);
	for(ll i = 0; i < n; i++){
		res[i] = r[i];
	}
	for(ll i = n; i--;){
		ll x = w[g[i][0]];
		for(ll u : g[i]){
			if(a[i]) x |= res[u];
			else x &= res[u];
		}
		res[i] = x;
	}
	return res;
}
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]);
	}
	if(sub1) return solve1(a, r, v, u);
	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 5 ms 1228 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 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 584 ms 69844 KB Output is correct
2 Correct 591 ms 69828 KB Output is correct
3 Correct 667 ms 69748 KB Output is correct
4 Correct 1641 ms 135696 KB Output is correct
5 Correct 1261 ms 136044 KB Output is correct
6 Correct 1324 ms 69512 KB Output is correct
7 Correct 838 ms 69500 KB Output is correct
8 Correct 609 ms 70232 KB Output is correct
9 Correct 746 ms 70468 KB Output is correct
10 Correct 643 ms 70068 KB Output is correct
11 Correct 628 ms 37476 KB Output is correct
12 Correct 106 ms 8500 KB Output is correct
13 Correct 1625 ms 135556 KB Output is correct
14 Correct 1610 ms 135500 KB Output is correct
15 Correct 1623 ms 135416 KB Output is correct
16 Correct 1608 ms 135520 KB Output is correct
17 Correct 1639 ms 135432 KB Output is correct
18 Correct 1047 ms 69348 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 826 ms 2540 KB Output is correct
2 Correct 292 ms 20492 KB Output is correct
3 Correct 316 ms 19944 KB Output is correct
4 Correct 134 ms 8372 KB Output is correct
5 Correct 732 ms 70492 KB Output is correct
6 Correct 703 ms 36484 KB Output is correct
7 Correct 677 ms 36744 KB Output is correct
8 Correct 271 ms 20504 KB Output is correct
9 Correct 48 ms 2380 KB Output is correct
10 Correct 1070 ms 4404 KB Output is correct
11 Correct 1064 ms 3284 KB Output is correct
12 Correct 1079 ms 4608 KB Output is correct
13 Correct 892 ms 69540 KB Output is correct
14 Correct 560 ms 36372 KB Output is correct

Subtask #5
0 / 12.0

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