# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
197482 | dndhk | Senior Postmen (BOI14_postmen) | C++14 | 797 ms | 67460 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>
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAX_N = 500000;
int N, M;
vector<int> gp[MAX_N+1];
bool chk[MAX_N+1];
pii p[MAX_N+1];
vector<int> v;
vector<int> nxt[MAX_N+1];
bool vst[MAX_N+1];
vector<int> vt;
int main(){
scanf("%d%d", &N, &M);
for(int i=1; i<=M; i++){
int a, b; scanf("%d%d", &a, &b);
gp[a].pb(i);
gp[b].pb(i);
p[i] = {a, b};
}
for(int i=1; i<=N; i++){
for(int j=0; j<gp[i].size(); j+=2){
nxt[gp[i][j]].pb(gp[i][j+1]);
nxt[gp[i][j+1]].pb(gp[i][j]);
}
}
for(int i=1; i<=M; i++){
if(!chk[i]){
chk[i] = true;
chk[nxt[i][0]] = true;
v.pb(nxt[i][0]);
v.pb(i);
int n = nxt[i][1];
while(1){
chk[n] = true;
v.pb(n);
if(chk[nxt[n][0]] && chk[nxt[n][1]]){
break;
}
if(chk[nxt[n][0]]){
n = nxt[n][1];
}else{
n = nxt[n][0];
}
}
int x;
if(p[v.back()].first==p[v[v.size()-2]].first || p[v.back()].first==p[v[v.size()-2]].second){
x = p[v.back()].second;
}else{
x = p[v.back()].first;
}
while(!v.empty()){
x = p[v.back()].first+p[v.back()].second-x;
if(vst[x]){
while(vt.back()!=x){
vst[vt.back()] = false;
printf("%d ", vt.back());
vt.pop_back();
}
printf("%d\n", x);
}else{
vst[x] = true;
vt.pb(x);
}
v.pop_back();
}
while(!vt.empty()){
vst[vt.back()] = false;
printf("%d ", vt.back());
vt.pop_back();
}printf("\n");
}
}
return 0;
}
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... |