Submission #390047

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
390047	2021-04-15T06:31:40 Z	Keshi	Toy Train (IOI17_train)	C++17	11 / 100	1734 ms	135916 KB

train

//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);
}

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++){
		for(ll j = 0; j < n; j++){
			if(can[i][j] && w[j]) res[i] = 1;
		}
		if(sub4) res[i] ^= 1;
	}
	return res;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	572 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	473 ms	69800 KB	Output is correct
2	Correct	527 ms	69744 KB	Output is correct
3	Correct	560 ms	69740 KB	Output is correct
4	Correct	1734 ms	135312 KB	Output is correct
5	Correct	1294 ms	135916 KB	Output is correct
6	Correct	931 ms	69336 KB	Output is correct
7	Correct	942 ms	69396 KB	Output is correct
8	Correct	633 ms	70116 KB	Output is correct
9	Correct	555 ms	70372 KB	Output is correct
10	Correct	717 ms	69992 KB	Output is correct
11	Correct	578 ms	37480 KB	Output is correct
12	Correct	104 ms	8500 KB	Output is correct
13	Correct	1669 ms	135276 KB	Output is correct
14	Correct	1687 ms	135300 KB	Output is correct
15	Correct	1659 ms	135332 KB	Output is correct
16	Correct	1719 ms	135396 KB	Output is correct
17	Correct	1655 ms	135396 KB	Output is correct
18	Correct	846 ms	69472 KB	Output is correct