Submission #424965

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
424965	2021-06-12T12:01:45 Z	MeGustaElArroz23	Toy Train (IOI17_train)	C++14	11 / 100	873 ms	1476 KB

train


#include <cstdio>
#include <vector>
#include <cassert>

#include "train.h"
#include<bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;

void debug(vi v){
	for (int x:v) cerr << x << ' ';
	cerr<<'\n';
}

bool escaso1(vector<int> who){
	for (int x:who){
		if (x==0) return 0;
	}
	return 1;
}

vi caso_todos1(vector<int> who, vector<int> charge, vector<int> u, vector<int> v){
	int n=who.size();
	int m=u.size();
	vi sol(n);
	vvi conexiones(n);
	for (int i=0;i<m;i++){
		conexiones[u[i]].push_back(v[i]);
	}
	vector<bool> charging(n,false);
	vector<int> chargin;
	for (int i=0;i<n;i++){
		if (charge[i]) chargin.push_back(i);
	}
	//cerr<<0;
	for (int x:chargin){
		vector<bool> porvisitar(n,true);
		queue<int> cola;
		cola.push(x);
		bool T=true;
		while (cola.size()){
			//cerr<<1;
			int ac=cola.front();
			//cerr<< ' ' << ac << ' ' <<cola.size()<<'\n';
			//cerr<<2;
			cola.pop();
			//cerr<<3;
			if (porvisitar[ac]){
				//cerr<<4;
				porvisitar[ac]=false;
				//cerr<<5;
				for (int y:conexiones[ac]) cola.push(y);
				//cerr<<6;
			}
			else if (ac==x) T=false;
		}
		//cerr<<7;
		if (not T) charging[x]=true;
	}
	//cerr<<1;
	for (int x=0;x<n;x++){
		vector<bool> porvisitar(n,true);
		queue<int> cola;
		cola.push(x);
		bool T=true;
		while (cola.size() and T){
			int ac=cola.front();
			cola.pop();
			if (porvisitar[ac]){
				if(charging[ac]){
					T=false;
					break;
				} 
				porvisitar[ac]=false;
				for (int y:conexiones[ac]) cola.push(y);
			}
		}
		if (T){
			sol[x]=0;
		}
		else sol[x]=1;
	}
	return sol;
}

vector<int> who_wins(vector<int> who, vector<int> charge, vector<int> u, vector<int> v) {
	if (escaso1(who)) return caso_todos1(who,charge,u,v);
	return vi(0);
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	3 ms	460 KB	WA in grader: Wrong returned array size
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	204 KB	WA in grader: Wrong returned array size
2	Halted	0 ms	0 KB	-

Subtask #3
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	180 ms	1472 KB	Output is correct
2	Correct	184 ms	1464 KB	Output is correct
3	Correct	205 ms	1456 KB	Output is correct
4	Correct	294 ms	1476 KB	Output is correct
5	Correct	100 ms	1356 KB	Output is correct
6	Correct	637 ms	1456 KB	Output is correct
7	Correct	278 ms	1448 KB	Output is correct
8	Correct	131 ms	1424 KB	Output is correct
9	Correct	380 ms	1476 KB	Output is correct
10	Correct	99 ms	1372 KB	Output is correct
11	Correct	112 ms	1360 KB	Output is correct
12	Correct	36 ms	1284 KB	Output is correct
13	Correct	497 ms	1456 KB	Output is correct
14	Correct	548 ms	1468 KB	Output is correct
15	Correct	873 ms	1460 KB	Output is correct
16	Correct	122 ms	1468 KB	Output is correct
17	Correct	86 ms	1468 KB	Output is correct
18	Correct	351 ms	1068 KB	Output is correct