oj.uz

Submission #425002

# Submission time Handle Problem Language Result Execution time Memory
425002 2021-06-12T12:20:18 Z MeGustaElArroz23 Toy Train (IOI17_train) C++14
22 / 100
 1354 ms 1488 KB 

#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]=1;
		}
		else sol[x]=0;
	}
	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 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 200 ms 1300 KB Output is correct
2 Correct 212 ms 1228 KB Output is correct
3 Correct 249 ms 1280 KB Output is correct
4 Correct 300 ms 1260 KB Output is correct
5 Correct 121 ms 1244 KB Output is correct
6 Correct 676 ms 1240 KB Output is correct
7 Correct 267 ms 1232 KB Output is correct
8 Correct 183 ms 1200 KB Output is correct
9 Correct 435 ms 1192 KB Output is correct
10 Correct 122 ms 1180 KB Output is correct
11 Correct 127 ms 1176 KB Output is correct
12 Correct 39 ms 1120 KB Output is correct
13 Correct 480 ms 1260 KB Output is correct
14 Correct 609 ms 1244 KB Output is correct
15 Correct 1052 ms 1248 KB Output is correct
16 Correct 137 ms 1244 KB Output is correct
17 Correct 93 ms 1244 KB Output is correct
18 Correct 410 ms 948 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1004 ms 1100 KB Output is correct
2 Correct 212 ms 1336 KB Output is correct
3 Correct 227 ms 1488 KB Output is correct
4 Correct 77 ms 1452 KB Output is correct
5 Correct 652 ms 1432 KB Output is correct
6 Correct 610 ms 1432 KB Output is correct
7 Correct 570 ms 1408 KB Output is correct
8 Correct 180 ms 1412 KB Output is correct
9 Correct 47 ms 1356 KB Output is correct
10 Correct 1326 ms 1468 KB Output is correct
11 Correct 1354 ms 1484 KB Output is correct
12 Correct 1266 ms 1476 KB Output is correct
13 Correct 759 ms 1460 KB Output is correct
14 Correct 428 ms 1364 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 51.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 -