Submission #613937

#TimeUsernameProblemLanguageResultExecution timeMemory
613937Richem장난감 기차 (IOI17_train)C++14
100 / 100
884 ms25316 KiB
#include <iostream> #include <vector> using namespace std; const int MAX_SOMMET = 5042; bool gagnant[MAX_SOMMET] = {0}; int qui[MAX_SOMMET]; bool recharge[MAX_SOMMET]; int nbSommet, nbArete; vector<int> adj[MAX_SOMMET]; int nbSortant[MAX_SOMMET] = {0}; bool acces[MAX_SOMMET] = {0}; int premier = 1; bool mAdj[MAX_SOMMET][MAX_SOMMET] = {0}; void dfs(int sommet, int type) { if((type == 1 && acces[sommet]) || (type == 2 && gagnant[sommet])) return; if(!premier && type == 1) acces[sommet] = 1; if(type == 2) gagnant[sommet] = 1; premier = 0; for(auto voisin : adj[sommet]) { if(qui[voisin] == 1) dfs(voisin, type); else { nbSortant[voisin] -= mAdj[sommet][voisin]; mAdj[sommet][voisin] = 0; if(nbSortant[voisin] == 0) dfs(voisin, type); } } } void resetSortant() { premier = 1; for(int sommet = 0; sommet < nbSommet; sommet++) { nbSortant[sommet] = 0; acces[sommet] = 0; } for(int sommet = 0; sommet < nbSommet; sommet++) { for(auto voisin : adj[sommet]) { nbSortant[voisin]++; mAdj[sommet][voisin] = 1; } } } vector<int> rep; vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) { nbSommet = a.size(); nbArete = u.size(); for(int i = 0; i < nbSommet; i++) { gagnant[i] = 0; qui[i] = a[i]; recharge[i] = r[i]; } for(int id = 0; id < nbArete; id++) { adj[v[id]].push_back(u[id]); } int nbPerdu = 0; resetSortant(); do { nbPerdu = 0; resetSortant(); for(int sommet = 0; sommet < nbSommet; sommet++) { if(recharge[sommet]) { dfs(sommet, 1); premier = 1; } } for(int sommet = 0; sommet < nbSommet; sommet++) { if(recharge[sommet] && !acces[sommet]) { nbPerdu++; recharge[sommet] = 0; } } } while(nbPerdu > 0); resetSortant(); for(int sommet = 0; sommet < nbSommet; sommet++) { if(recharge[sommet]) dfs(sommet, 2); } for(int sommet = 0; sommet < nbSommet; sommet++) { rep.push_back(gagnant[sommet]); //cout << gagnant[sommet] <<" "; } return rep; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...