| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1126037 | alecurse | 열대 식물원 (Tropical Garden) (IOI11_garden) | C++20 | 0 ms | 0 KiB |
#include <vector>
#include <iostream>
#include <queue>
using namespace std;
int N, M, P, Q;
struct Arco {
int to=-1;
int lcycle=0;
int ltocycle=0;
int startcycle=0;
};
vector<vector<bool> > vis;
vector<vector<int> > pth;
vector<vector<int> > adj;
vector<vector<Arco> > sol;
int current = 0;
int untilreached = -1;
Arco tosolve;
void dfs(int x, int e, int th) {
if(e!=-1) {
if(vis[e][th]) {
// do stuff;
if(sol[e][th].to==-1) {
sol[e][th].to=x;
sol[e][th].lcycle=current+1-pth[e][th];
sol[e][th].ltocycle=0;
sol[e][th].startcycle=e;
untilreached=e;
tosolve=sol[e][th];
return;
}
tosolve = sol[e][th];
return;
}
vis[e][th]=true;
pth[e][th]=current;
current++;
}
if(adj[x][1]==-1||adj[x][0]!=e) {
dfs(adj[x][0],x,0);
} else {
dfs(adj[x][1],x,1);
}
if(e!=-1) {
if(untilreached==-1) {
sol[e][th]=tosolve;
tosolve.to = x;
tosolve.ltocycle++;
} else {
sol[e][th]=tosolve;
tosolve.to = x;
tosolve.startcycle=e;
if(untilreached==e) {
untilreached=-1;
}
}
tosolve=sol[e][th];
}
}
int main() {
cin>>N>>M>>P;
adj.assign(N, vector<int> (2,-1));
vis.resize(N, vector<bool> (2));
pth.resize(N, vector<int> (2));
sol.resize(N, vector<Arco> (2));
for(int i=0;i<M;i++) {
int a,b;
cin>>a>>b;
if(adj[a][0]==-1) {
adj[a][0]=b;
} else if(adj[a][1]==-1) {
adj[a][1]=b;
}
if(adj[b][0]==-1) {
adj[b][0]=a;
} else if(adj[b][1]==-1) {
adj[b][1]=a;
}
}
for(int i=0;i<N;i++) {
if(adj[i][0]!=-1) {
if(sol[i][0].to!=-1)
continue;
Arco nuovo;
tosolve=nuovo;
untilreached=-1;
dfs(i,-1,-1);
}
}
}