Submission #424186

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
424186	2021-06-11T17:46:52 Z	cfalas	Toy Train (IOI17_train)	C++14	0 / 100	1165 ms	37332 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;

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;
			FOA(x,path){
				if(v==x) start = true;
				if(start) ap.push_back(x);
			}
			loops.push_back(ap);
		}
	}
	spath.erase(s);
	path.erase(path.end()-1);
}

vi who_wins(vi a, vi r, vi u, vi v) {
	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){
		bool win = false;
		//cout<<loop.F<<" "<<loop.S<<": ";
		FOA(v,loop){
			if(r[v]) win = true;
			//cout<<v<<" ";
		}
		//cout<<endl;
		if(win){
			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	71 ms	1996 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	1996 KB	Output is correct
2	Correct	11 ms	1880 KB	Output is correct
3	Correct	12 ms	1872 KB	Output is correct
4	Correct	1165 ms	23076 KB	Output is correct
5	Correct	579 ms	13252 KB	Output is correct
6	Correct	15 ms	2968 KB	Output is correct
7	Correct	395 ms	1656 KB	Output is correct
8	Correct	13 ms	1372 KB	Output is correct
9	Correct	10 ms	1484 KB	Output is correct
10	Correct	11 ms	1356 KB	Output is correct
11	Correct	10 ms	1356 KB	Output is correct
12	Correct	10 ms	1612 KB	Output is correct
13	Correct	426 ms	37332 KB	Output is correct
14	Incorrect	94 ms	36548 KB	3rd lines differ - on the 1st token, expected: '1', found: '0'
15	Halted	0 ms	0 KB	-