답안 #424990

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
424990	2021-06-12T12:15:13 Z	MeGustaElArroz23	장난감 기차 (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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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