Submission #607453

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
607453	2022-07-26T17:44:08 Z	Arturgo	Toy Train (IOI17_train)	C++17	11 / 100	253 ms	1492 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;
		}
		score = min(score, nbRecharges + 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	Incorrect	5 ms	1108 KB	3rd lines differ - on the 1st token, expected: '0', found: '1'
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	212 KB	3rd lines differ - on the 8th token, expected: '0', found: '1'
2	Halted	0 ms	0 KB	-

Subtask #3
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	72 ms	1456 KB	Output is correct
2	Correct	135 ms	1444 KB	Output is correct
3	Correct	171 ms	1364 KB	Output is correct
4	Correct	253 ms	1388 KB	Output is correct
5	Correct	77 ms	1364 KB	Output is correct
6	Correct	12 ms	1492 KB	Output is correct
7	Correct	181 ms	1376 KB	Output is correct
8	Correct	8 ms	1364 KB	Output is correct
9	Correct	6 ms	1364 KB	Output is correct
10	Correct	12 ms	1376 KB	Output is correct
11	Correct	9 ms	1408 KB	Output is correct
12	Correct	6 ms	1364 KB	Output is correct
13	Correct	8 ms	1344 KB	Output is correct
14	Correct	9 ms	1364 KB	Output is correct
15	Correct	9 ms	1384 KB	Output is correct
16	Correct	9 ms	1380 KB	Output is correct
17	Correct	9 ms	1364 KB	Output is correct
18	Correct	127 ms	1128 KB	Output is correct