이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <vector>
#include <iostream>
#include <set>
using namespace std;
int nbPieces, nbRoutes;
vector<int> ordre;
vector<int> parents[300 * 1000];
int curPasse;
int derPasse[300 * 1000];
int curDate;
int date[300 * 1000];
void dfs(int piece) {
if(derPasse[piece] == curPasse)
return;
derPasse[piece] = curPasse;
for(int parent : parents[piece])
dfs(parent);
ordre.push_back(piece);
}
bool cles[300 * 1000];
vector<int> sommetsVus[300 * 1000];
vector<int> aNettoyer;
vector<int> c, r;
vector<pair<int, int>> voisins[300 * 1000];
int minNbVus = 1000 * 1000 * 1000;
vector<int> reponse;
void explore(int piece) {
vector<int> sommetsOks;
sommetsOks.push_back(piece);
bool accedeAutre = false;
vector<int> vus;
curDate++;
while(!sommetsOks.empty()) {
int sommet = sommetsOks.back();
sommetsOks.pop_back();
if(date[sommet] == curDate)
continue;
if(date[sommet] != 0) {
accedeAutre = true;
continue;
}
vus.push_back(sommet);
date[sommet] = curDate;
cles[r[sommet]] = true;
aNettoyer.push_back(r[sommet]);
for(int sommet : sommetsVus[r[sommet]]) {
sommetsOks.push_back(sommet);
}
sommetsVus[r[sommet]].clear();
for(pair<int, int> voisin : voisins[sommet]) {
if(cles[voisin.second])
sommetsOks.push_back(voisin.first);
else {
sommetsVus[voisin.second].push_back(voisin.first);
aNettoyer.push_back(voisin.second);
}
}
}
while(!aNettoyer.empty()) {
int pos = aNettoyer.back();
aNettoyer.pop_back();
sommetsVus[pos].clear();
cles[pos] = false;
}
if(accedeAutre)
return;
if(vus.size() < minNbVus) {
minNbVus = vus.size();
reponse.clear();
}
if(vus.size() == minNbVus) {
for(int vu : vus) {
reponse.push_back(vu);
}
}
}
vector<int> find_reachable(vector<int> _r, vector<int> u, vector<int> v, vector<int> _c) {
c = _c;
r = _r;
int nbPieces = r.size();
int nbRoutes = u.size();
for(int iRoute = 0;iRoute < nbRoutes;iRoute++) {
if(c[iRoute] == r[u[iRoute]])
parents[v[iRoute]].push_back(u[iRoute]);
if(c[iRoute] == r[v[iRoute]])
parents[u[iRoute]].push_back(v[iRoute]);
voisins[u[iRoute]].push_back({v[iRoute], c[iRoute]});
voisins[v[iRoute]].push_back({u[iRoute], c[iRoute]});
}
curPasse++;
for(int iPiece = 0;iPiece < nbPieces;iPiece++) {
dfs(iPiece);
}
while(!ordre.empty()) {
int piece = ordre.back();
ordre.pop_back();
explore(piece);
}
vector<int> ans(nbPieces, 0);
for(int x : reponse)
ans[x] = 1;
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
keys.cpp: In function 'void explore(int)':
keys.cpp:89:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
89 | if(vus.size() < minNbVus) {
| ~~~~~~~~~~~^~~~~~~~~~
keys.cpp:93:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
93 | if(vus.size() == minNbVus) {
| ~~~~~~~~~~~^~~~~~~~~~~
# | 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... |