Submission #424191

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
424191	2021-06-11T17:50:28 Z	cfalas	Toy Train (IOI17_train)	C++14	0 / 100	1091 ms	23108 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){
		if(!vis[i]) dfs(i);
	}

	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	60 ms	2096 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	1940 KB	Output is correct
2	Correct	11 ms	1868 KB	Output is correct
3	Correct	11 ms	1764 KB	Output is correct
4	Correct	1091 ms	23108 KB	Output is correct
5	Correct	534 ms	13068 KB	Output is correct
6	Correct	14 ms	1484 KB	Output is correct
7	Correct	361 ms	1656 KB	Output is correct
8	Correct	11 ms	1484 KB	Output is correct
9	Correct	10 ms	1480 KB	Output is correct
10	Correct	12 ms	1364 KB	Output is correct
11	Correct	10 ms	1356 KB	Output is correct
12	Correct	10 ms	1356 KB	Output is correct
13	Correct	395 ms	12412 KB	Output is correct
14	Incorrect	60 ms	1996 KB	3rd lines differ - on the 1st token, expected: '1', found: '0'
15	Halted	0 ms	0 KB	-