Submission #1080384

#TimeUsernameProblemLanguageResultExecution timeMemory
1080384oscar1fSeptember (APIO24_september)C++17
0 / 100
2 ms5468 KiB
#include<bits/stdc++.h> #include "september.h" using namespace std; const int MAX_SOM=100*1000+5; vector<int> adja[MAX_SOM],adjaTrans[MAX_SOM]; vector<int> ordre; int nbCompo; bool dv[MAX_SOM]; int numCompo[MAX_SOM]; void addAre(int deb,int fin) { adja[deb].push_back(fin); adjaTrans[fin].push_back(deb); } void DFS(int pos) { if (!dv[pos]) { dv[pos]=true; for (int i:adja[pos]) { DFS(i); } ordre.push_back(pos); } } void DFS_trans(int pos) { if (numCompo[pos]==0) { numCompo[pos]=nbCompo; for (int i:adjaTrans[pos]) { DFS_trans(i); } } } int solve(int nbSom,int nbPers,vector<int> pere,vector<vector<int>> S) { for (int i=0;i<nbSom;i++) { adja[i].clear(); adjaTrans[i].clear(); } for (int i=0;i<nbSom;i++) { addAre(pere[i],i); } for (int i=0;i<nbPers;i++) { for (int j=0;j<nbSom-2;j++) { addAre(S[i][j],S[i][j+1]); } } nbCompo=0; ordre.clear(); for (int i=0;i<nbSom;i++) { dv[i]=false; numCompo[i]=0; } for (int i=0;i<nbSom;i++) { DFS(i); } reverse(ordre.begin(),ordre.end()); for (int i:ordre) { if (numCompo[i]==0) { nbCompo++; DFS_trans(i); } } /*for (int i=0;i<nbSom;i++) { cout<<numCompo[i]<<" "; } cout<<endl;*/ return nbCompo-1; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...