#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define FOR(i,a) for (int i=0;i<(a);++i)
#define FORD(i,a) for (int i=(a)-1;i>=0;i--)
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
#define FORTD(i,b,a) for (int i=(b);i>=(a);--i)
#define trav(i,v) for (auto i : v)
#define all(v) v.begin(),v.end()
#define ad push_back
#define fr first
#define sc second
#define mpr(a,b) make_pair(a,b)
#define pir pair<int,int>
#define all(v) v.begin(),v.end()
#define make_unique(v) v.erase(unique(all(v)),v.end())
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define srng mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define y1 EsiHancagorcRepa
class fastIO{
private:
long long P10[19];
public:
fastIO(){
P10[0]=1;
for (int i=1;i<=18;++i){
P10[i]=P10[i-1]*10;
}
}
long long read() {
char ch=getchar();
long long mul=1;
if (ch=='-'){
mul=-1;
ch=getchar();
}
long long pat=0;
while(ch==10 || ch==32)ch=getchar();
while(ch>='0' && ch<='9'){
pat=pat*10ll+(long long)(ch-'0');
//cout<<ch<<endl;
ch=getchar();
}
return pat*mul;
}
char readCh(){
char ch=getchar();
while(ch==10 || ch==32)ch=getchar();
return ch;
}
void readStr(string &s){
s="";
char ch=getchar();
while(ch==10 || ch==32)ch=getchar();
while(ch!=10 && ch!=32){
s+=ch;
ch=getchar();
}
}
void writeInt(int k,bool aft=false){
if (k==0){
putchar('0');
putchar(32);
return;
}
if (k<0){
k=-k;
putchar('-');
}
bool zro=false;
for (int i=9;i>=0;--i){
int tv=k/P10[i];
k%=P10[i];
if (tv==0 && !zro)continue;
zro=true;
putchar(tv+'0');
}
if (!aft) putchar(32);
}
void writeLL(long long k,bool aft=false){
if (k==0){
putchar('0');
putchar(32);
return;
}
if (k<0){
k=-k;
putchar('-');
}
bool zro=false;
for (int i=18;i>=0;--i){
int tv=k/P10[i];
k%=P10[i];
if (tv==0 && !zro)continue;
zro=true;
putchar(tv+'0');
}
if (!aft) putchar(32);
}
void writeStr(string &s,bool aft=false){
int sz=s.length();
for (int i=0;i<sz;++i){
putchar(s[i]);
}
if (!aft) putchar(32);
}
void writechar(char k){
putchar(k);
}
void space(){
putchar(32);
}
void nwLn(){
putchar(10);
}
} io;
const int N=5e5+10;
const ll MOD=1e9+7;
vector<pir> g[N];
vector<int> ans[N],eu;
bool fr[N],col[N];
int main(){
fastio;
srng;
int n=io.read(),m=io.read();
//cin>>n>>m;
FOR(i,m){
int a=io.read(),b=io.read();
//cin>>a>>b;
g[a].ad({b,i});
g[b].ad({a,i});
}
vector<int> st;
st.ad(1);
while(st.size()){
int v=st.back();
//st.pop_back();
//cout<<v<<" "<<g[v].size()<<endl;
while(g[v].size() && col[g[v].back().sc])g[v].pop_back();
if (!g[v].size()){
st.pop_back();
eu.ad(v);
continue;
}
int to=g[v].back().fr,kox=g[v].back().sc;
col[kox]=true;
g[v].pop_back();
st.ad(to);
}
int cnt=0;
//cout<<eu.size()<<endl;
FOR(i,eu.size()){
//cout<<eu[i]<<" ";
if (fr[eu[i]]){
ans[cnt].ad(eu[i]);
while(st.size() && st.back()!=eu[i]){
fr[st.back()]=false;
ans[cnt].ad(st.back());
st.pop_back();
}
cnt++;
}
else{
fr[eu[i]]=true;
st.ad(eu[i]);
}
}
//cout<<endl;
FOR(i,cnt){
trav(tv,ans[i])io.writeInt(tv);
io.nwLn();
}
return 0;
}
Compilation message
postmen.cpp: In function 'int main()':
postmen.cpp:8:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define FOR(i,a) for (int i=0;i<(a);++i)
^
postmen.cpp:164:5: note: in expansion of macro 'FOR'
FOR(i,eu.size()){
^~~
postmen.cpp:137:9: warning: unused variable 'n' [-Wunused-variable]
int n=io.read(),m=io.read();
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
23808 KB |
Output is correct |
2 |
Correct |
19 ms |
23808 KB |
Output is correct |
3 |
Correct |
17 ms |
23808 KB |
Output is correct |
4 |
Correct |
23 ms |
24064 KB |
Output is correct |
5 |
Correct |
17 ms |
23936 KB |
Output is correct |
6 |
Correct |
0 ms |
24064 KB |
Output is correct |
7 |
Correct |
23 ms |
24576 KB |
Output is correct |
8 |
Correct |
20 ms |
23984 KB |
Output is correct |
9 |
Correct |
45 ms |
27568 KB |
Output is correct |
10 |
Correct |
19 ms |
23936 KB |
Output is correct |
11 |
Correct |
24 ms |
24012 KB |
Output is correct |
12 |
Correct |
50 ms |
27892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
23808 KB |
Output is correct |
2 |
Correct |
24 ms |
23808 KB |
Output is correct |
3 |
Correct |
19 ms |
23784 KB |
Output is correct |
4 |
Correct |
19 ms |
23936 KB |
Output is correct |
5 |
Correct |
21 ms |
23936 KB |
Output is correct |
6 |
Correct |
23 ms |
24040 KB |
Output is correct |
7 |
Correct |
22 ms |
24576 KB |
Output is correct |
8 |
Correct |
18 ms |
23936 KB |
Output is correct |
9 |
Correct |
50 ms |
27488 KB |
Output is correct |
10 |
Correct |
29 ms |
24116 KB |
Output is correct |
11 |
Correct |
30 ms |
23936 KB |
Output is correct |
12 |
Correct |
48 ms |
27892 KB |
Output is correct |
13 |
Correct |
84 ms |
29040 KB |
Output is correct |
14 |
Correct |
88 ms |
28748 KB |
Output is correct |
15 |
Correct |
78 ms |
28948 KB |
Output is correct |
16 |
Correct |
81 ms |
29128 KB |
Output is correct |
17 |
Correct |
83 ms |
28784 KB |
Output is correct |
18 |
Correct |
80 ms |
29064 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
23808 KB |
Output is correct |
2 |
Correct |
24 ms |
23780 KB |
Output is correct |
3 |
Correct |
18 ms |
23808 KB |
Output is correct |
4 |
Correct |
24 ms |
24064 KB |
Output is correct |
5 |
Correct |
18 ms |
23936 KB |
Output is correct |
6 |
Correct |
19 ms |
24120 KB |
Output is correct |
7 |
Correct |
21 ms |
24552 KB |
Output is correct |
8 |
Correct |
22 ms |
23936 KB |
Output is correct |
9 |
Correct |
46 ms |
27560 KB |
Output is correct |
10 |
Correct |
21 ms |
24064 KB |
Output is correct |
11 |
Correct |
22 ms |
24012 KB |
Output is correct |
12 |
Correct |
55 ms |
27924 KB |
Output is correct |
13 |
Correct |
82 ms |
29016 KB |
Output is correct |
14 |
Correct |
83 ms |
28724 KB |
Output is correct |
15 |
Correct |
67 ms |
28908 KB |
Output is correct |
16 |
Correct |
85 ms |
29124 KB |
Output is correct |
17 |
Correct |
85 ms |
28788 KB |
Output is correct |
18 |
Correct |
81 ms |
29104 KB |
Output is correct |
19 |
Correct |
492 ms |
49844 KB |
Output is correct |
20 |
Correct |
469 ms |
48716 KB |
Output is correct |
21 |
Correct |
410 ms |
49728 KB |
Output is correct |
22 |
Correct |
480 ms |
49940 KB |
Output is correct |
23 |
Correct |
155 ms |
41260 KB |
Output is correct |
24 |
Execution timed out |
546 ms |
49284 KB |
Time limit exceeded |
25 |
Halted |
0 ms |
0 KB |
- |