Submission #607448

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
607448	2022-07-26T17:40:29 Z	Arturgo	Toy Train (IOI17_train)	C++17	0 / 100	2000 ms	1496 KB

train

#include "train.h"
#include <deque>
#include <vector>
using namespace std;

vector<int> who_wins(vector<int> estMax, vector<int> estRecharge,
 vector<int> debs, vector<int> fins) {
	int nbSommets = estMax.size();
	
	vector<int> aggregs(nbSommets, 0);
	vector<int> nbMins(nbSommets, 0);
	
	vector<int> scores(nbSommets, 0);
	vector<bool> estDans(nbSommets, true);
	
	vector<vector<int>> fils(nbSommets);
	vector<vector<int>> parents(nbSommets);
	
	for(int iArc = 0;iArc < (int)debs.size();iArc++) {
		fils[debs[iArc]].push_back(fins[iArc]);
		parents[fins[iArc]].push_back(debs[iArc]);
	}
	
	int nbRecharges = 0;
	
	deque<int> file;
	for(int iSommet = 0;iSommet < nbSommets;iSommet++) {
		file.push_back(iSommet);
		
		if(estRecharge[iSommet])
			nbRecharges += 1;
	}
	
	while(!file.empty()) {
		int sommet = file.back();
		file.pop_back();
		estDans[sommet] = false;
		
		int score;
		if(estMax[sommet]) {
			score = 0;
			
			for(int fil : fils[sommet]) {
				score = max(score, scores[fil]);
			}
		}
		else {
			score = nbRecharges + 1;
			int nb = 0;
			
			for(int fil : fils[sommet]) {
				if(score < scores[fil]) {
					score = scores[fil];
					nb = 0;
				}
				
				if(score == scores[fil]) {
					nb++;
				}
			}
			
			nbMins[sommet] = nb;
		}
		
		aggregs[sommet] = score;
		if(estRecharge[sommet]) {
			score += 1;
		}
		scores[sommet] = score;
		
		for(int parent : parents[sommet]) {
			if(estDans[parent]) continue;
			
			if(estMax[parent] && score > aggregs[parent]) {
				file.push_front(parent);
				estDans[parent] = true;
			}
			
			if(!estMax[parent] && score == aggregs[parent]) {
				nbMins[parent]--;
				
				if(nbMins[parent] == 0) {
					file.push_front(parent);
					estDans[parent] = true;
				}
			}
		}
	}
	
	vector<int> estGagnant;
	
	for(int iSommet = 0;iSommet < nbSommets;iSommet++) {
		estGagnant.push_back(scores[iSommet] >= nbRecharges + 1);
	}
	
	return estGagnant;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2074 ms	980 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	212 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	73 ms	1496 KB	Output is correct
2	Correct	126 ms	1432 KB	Output is correct
3	Correct	168 ms	1420 KB	Output is correct
4	Execution timed out	2091 ms	1364 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-