Submission #390045

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
390045	2021-04-15T06:27:00 Z	Keshi	Toy Train (IOI17_train)	C++17	11 / 100	1751 ms	136352 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] = 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	534 ms	68752 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	478 ms	69804 KB	Output is correct
2	Correct	521 ms	69708 KB	Output is correct
3	Correct	575 ms	69756 KB	Output is correct
4	Correct	1730 ms	135496 KB	Output is correct
5	Correct	1390 ms	136352 KB	Output is correct
6	Correct	946 ms	69512 KB	Output is correct
7	Correct	938 ms	69736 KB	Output is correct
8	Correct	583 ms	70400 KB	Output is correct
9	Correct	566 ms	70476 KB	Output is correct
10	Correct	706 ms	70136 KB	Output is correct
11	Correct	587 ms	37844 KB	Output is correct
12	Correct	119 ms	8608 KB	Output is correct
13	Correct	1716 ms	135556 KB	Output is correct
14	Correct	1751 ms	135616 KB	Output is correct
15	Correct	1682 ms	135616 KB	Output is correct
16	Correct	1650 ms	135568 KB	Output is correct
17	Correct	1661 ms	135544 KB	Output is correct
18	Correct	834 ms	69512 KB	Output is correct