# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
31546 | ngkan146 | Senior Postmen (BOI14_postmen) | C++98 | 308 ms | 16632 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int ctrl[500005];
int nxt[500005], prv[500005], id[1000005];
int head[500005], en[500005];
bool visited[1000005];
int n,m;
int euler[1000005], eulersize;
int q[1000005], qsize;
void dfs(){
q[qsize++] = 1;
while(qsize){
int u = q[qsize-1];
bool mjk = 0;
for(;ctrl[u];ctrl[u] = nxt[ctrl[u]]){
int v = (u ^ head[id[ctrl[u]]] ^ en[id[ctrl[u]]]);
if (visited[id[ctrl[u]]]) continue;
mjk = 1;
visited[id[ctrl[u]]] = 1;
q[qsize++] = v;
break;
}
if(mjk) continue;
euler[eulersize++] = u;
--qsize;
}
}
int st[1000005], stsize;
bool used[1000005];
int main(){
scanf("%d %d",&n,&m);
int cnt = 0;
for(int i=1;i<=m;++i){
int x,y;
scanf("%d %d",&x,&y);
if (!ctrl[x]){
ctrl[x] = ++cnt;
id[cnt] = i;
prv[x] = cnt;
}
else
nxt[prv[x]] = ++cnt,
id[cnt] = i,
prv[x] = cnt;
if (!ctrl[y]){
ctrl[y] = ++cnt;
id[cnt] = i;
prv[y] = cnt;
}
else
nxt[prv[y]] = ++cnt,
id[cnt] = i,
prv[y] = cnt;
head[i] = x;
en[i] = y;
}
dfs();
for(int i=0;i<eulersize;++i){
if (used[euler[i]]){
while(st[stsize-1] != euler[i]){
printf("%d ",st[stsize-1]);
used[st[stsize-1]] = 0;
--stsize;
};
printf("%d\n",euler[i]);
}
else{
st[stsize++] = euler[i];
used[euler[i]] = 1;
}
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |