제출 #1080359

#제출 시각아이디문제언어결과실행 시간메모리
1080359oscar1f9월 (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=1;i<nbSom;i++) { if (pere[i]!=0) { 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=1;i<nbSom;i++) { dv[i]=false; numCompo[i]=0; } for (int i=1;i<nbSom;i++) { DFS(i); } reverse(ordre.begin(),ordre.end()); for (int i:ordre) { if (numCompo[i]==0) { nbCompo++; DFS_trans(i); } } return nbCompo; }
#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...