Submission #424990

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
424990	2021-06-12T12:15:13 Z	MeGustaElArroz23	Toy Train (IOI17_train)	C++14	11 / 100	896 ms	1584 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;
}

bool escaso2(vector<int> who){
	for (int x:who){
		if (x==1) 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;
}

vi caso_todos2(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=0;x<n;x++){
		vector<int> porvisitar=charge;
		for (int i=0;i<n;i++) porvisitar[i]=-porvisitar[i]+1;

		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 (charge[x]) T=true;
		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);
	else if (escaso2(who)) return caso_todos2(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	292 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	194 ms	1508 KB	Output is correct
2	Correct	232 ms	1584 KB	Output is correct
3	Correct	223 ms	1452 KB	Output is correct
4	Correct	336 ms	1356 KB	Output is correct
5	Correct	87 ms	1472 KB	Output is correct
6	Correct	701 ms	1468 KB	Output is correct
7	Correct	280 ms	1440 KB	Output is correct
8	Correct	143 ms	1408 KB	Output is correct
9	Correct	417 ms	1380 KB	Output is correct
10	Correct	122 ms	1384 KB	Output is correct
11	Correct	133 ms	1368 KB	Output is correct
12	Correct	36 ms	1320 KB	Output is correct
13	Correct	509 ms	1456 KB	Output is correct
14	Correct	602 ms	1460 KB	Output is correct
15	Correct	889 ms	1484 KB	Output is correct
16	Correct	129 ms	1456 KB	Output is correct
17	Correct	123 ms	1460 KB	Output is correct
18	Correct	389 ms	1072 KB	Output is correct