Submission #424218

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
424218	2021-06-11T18:09:31 Z	cfalas	Toy Train (IOI17_train)	C++14	0 / 100	1156 ms	23312 KB

train

#include "train.h"
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define INF 10000000
#define MOD 1000000007
#define MID ((l+r)/2)
#define HASHMOD 2305843009213693951
#define ll long long
#define ull unsigned long long
#define F first
#define S second
typedef pair<ll, ll> ii;
typedef pair<ii, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef map<int, int> mii;

#define EPS 1e-6
#define FOR(i,n) for(int i=0;i<((int)(n));i++)
#define FORi(i,a,b) for(int i=((int)(a));i<((int)(b));i++)
#define FOA(v, a) for(auto &v : a)
#define len(x) ((int)x.size())

vector<vi> adj;
vector<vi> rev;
vi vis;

vector<int> path;
vector<vi> loops;
set<int> spath;
vi r;

void dfs(int s){
	path.push_back(s);
	spath.insert(s);
	vis[s] = 1;
	for(auto v : adj[s]){
		if(!vis[v]) dfs(v);
		else if(spath.count(v)){
			bool start = false;
			vi ap;
			bool win = false;
			FOA(x,path){
				if(v==x) start = true;
				if(start) ap.push_back(x);
				if(start && r[x]) win = true;
			}
			if(win) loops.push_back(ap);
		}
	}
	spath.erase(s);
	path.erase(path.end()-1);
}

vi who_wins(vi a, vi rr, vi u, vi v) {
	r = rr;
	int n = len(a);
	adj.assign(n, vi());
	rev.assign(n, vi());
	vis.assign(n,0);
	vi res(n, 0);

	FOR(i, len(u)){
		adj[u[i]].push_back(v[i]);
		rev[v[i]].push_back(u[i]);
	}
	FOR(i,n){
		dfs(i);
		assert(path.size()==0);
	}

	FOA(loop, loops){
		queue<int> q;
		vi used(n, 0);
		FOA(v,loop) q.push(v), used[v] = true;
		while(!q.empty()){
			int t = q.front();
			q.pop();
			res[t] = 1;
			FOA(v,rev[t]){
				if(!used[v]){
					used[v] = true;
					q.push(v);
				}
			}
		}
	}

	return res;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	108 ms	2120 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	204 KB	3rd lines differ - on the 8th token, expected: '0', found: '1'
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	1868 KB	Output is correct
2	Correct	11 ms	2004 KB	Output is correct
3	Correct	12 ms	1996 KB	Output is correct
4	Correct	1156 ms	23312 KB	Output is correct
5	Correct	535 ms	13396 KB	Output is correct
6	Correct	15 ms	1612 KB	Output is correct
7	Correct	433 ms	1948 KB	Output is correct
8	Correct	12 ms	1612 KB	Output is correct
9	Correct	10 ms	1616 KB	Output is correct
10	Correct	12 ms	1612 KB	Output is correct
11	Correct	14 ms	1552 KB	Output is correct
12	Correct	11 ms	1448 KB	Output is correct
13	Correct	426 ms	12616 KB	Output is correct
14	Incorrect	81 ms	2200 KB	3rd lines differ - on the 1st token, expected: '1', found: '0'
15	Halted	0 ms	0 KB	-