Submission #1073225

#TimeUsernameProblemLanguageResultExecution timeMemory
1073225oscar1fToy Train (IOI17_train)C++17
11 / 100
6 ms1628 KiB
#include<bits/stdc++.h> #include "train.h" using namespace std; const int MAX_SOM=5000+5; int nbSom,nbAre; vector<int> rep,possed,charg; vector<int> adjaTrans[MAX_SOM]; int degSort[MAX_SOM][2]; int pb[MAX_SOM]; void DFS(int pos) { if (pb[pos]==0) { pb[pos]=1; for (int i:adjaTrans[pos]) { //cout<<"?"<<i<<endl; if (i!=pos) { if (possed[i]==1) { DFS(i); } else { degSort[i][0]--; if (degSort[i][0]==0) { DFS(i); } } } } } } void DFS2(int pos) { if (rep[pos]==1) { rep[pos]=0; for (int i:adjaTrans[pos]) { if (i!=pos) { if (possed[i]==0) { DFS2(i); } else { degSort[i][1]--; if (degSort[i][1]==0) { DFS2(i); } } } } } } vector<int> who_wins(vector<int> a,vector<int> r,vector<int> u,vector<int> v) { nbSom=a.size(); nbAre=u.size(); possed=a; charg=r; rep.resize(nbSom,1); for (int i=0;i<nbAre;i++) { adjaTrans[v[i]].push_back(u[i]); degSort[u[i]][0]++; degSort[u[i]][1]++; } for (int i=0;i<nbSom;i++) { if (charg[i]==1) { DFS(i); } } for (int i=0;i<nbSom;i++) { if (charg[i]==1) { DFS(i); } } /*for (int i=0;i<nbSom;i++) { cout<<pb[i]<<" "; } cout<<endl;*/ for (int i=0;i<nbSom;i++) { if (pb[i]==0) { DFS2(i); } } 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...