이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "september.h"
#include <bits/stdc++.h>
using namespace std;
int solve(
int nbSommets,
int nbOrdres,
vector<int> parents,
vector<vector<int>> ordres
) {
vector<vector<int>> sommetsAvant(nbSommets);
vector<vector<int>> sommetsApres(nbSommets);
auto ajoute = [&](int avant, int apres) {
sommetsAvant[apres].push_back(avant);
sommetsApres[avant].push_back(apres);
};
for(int u = 1;u < nbSommets;u++) {
ajoute(u, parents[u]);
}
for(vector<int>& ordre : ordres) {
for(int i = 1;i < (int)ordre.size();i++) {
ajoute(ordre[i - 1], ordre[i]);
}
}
vector<bool> estVu(nbSommets, false);
vector<int> postOrdre;
auto calc_ordre = [&](auto self, int u) -> void {
if(estVu[u]) return;
estVu[u] = true;
for(int v : sommetsAvant[u]) {
self(self, v);
}
postOrdre.push_back(u);
};
calc_ordre(calc_ordre, 0);
fill(estVu.begin(), estVu.end(), false);
auto calc_cfc = [&](auto self, int u) -> void {
if(estVu[u]) return;
estVu[u] = true;
for(int v : sommetsApres[u]) {
self(self, v);
}
};
int nbCFC = 0;
while(!postOrdre.empty()) {
int u = postOrdre.back();
postOrdre.pop_back();
if(!estVu[u]) {
calc_cfc(calc_cfc, u);
nbCFC++;
}
}
return nbCFC - 1;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |