Submission #424193

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
424193	2021-06-11T17:54:05 Z	cfalas	Toy Train (IOI17_train)	C++14	0 / 100	1130 ms	23100 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);
	}

	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	116 ms	2124 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	14 ms	1980 KB	Output is correct
2	Correct	16 ms	1872 KB	Output is correct
3	Correct	12 ms	1740 KB	Output is correct
4	Correct	1130 ms	23100 KB	Output is correct
5	Correct	567 ms	13064 KB	Output is correct
6	Correct	14 ms	1484 KB	Output is correct
7	Correct	388 ms	1664 KB	Output is correct
8	Correct	11 ms	1484 KB	Output is correct
9	Correct	10 ms	1484 KB	Output is correct
10	Correct	12 ms	1384 KB	Output is correct
11	Correct	13 ms	1364 KB	Output is correct
12	Correct	10 ms	1228 KB	Output is correct
13	Correct	400 ms	12424 KB	Output is correct
14	Incorrect	66 ms	2000 KB	3rd lines differ - on the 1st token, expected: '1', found: '0'
15	Halted	0 ms	0 KB	-