#include <bits/stdc++.h>
/**
|||||||||| ||||| ||||| ||||||||||
||||||||||||| ||||| ||||| |||||
|||| |||||| ||||| ||||| |||||
||||||||||||||||| ||||||||||||||| ||||||||||
||||||||||||||||||| ||||||||||||||| |||||
||||| ||||| ||||| ||||| |||||
||||| ||||| ||||| ||||| ||||||||||
AHMED;HASSAN;SAEED;
*/
#define int long long
using namespace std;
/**
struct sgtree1d{
vector<int>tree,adr;
int sz=1;
void init(int n){
while(sz<=n)sz<<=1;
adr=tree=vector<int>(2*sz,0);
}
void updt(int idx,int val,int x,int lx,int rx){
///cout<<lx<<' '<<rx<<'\n';
if(rx<idx||lx>idx)return ;
if(lx==rx){
tree[x]=val;
return ;
}
int mid=(lx+rx)/2;
updt(idx,val,2*x,lx,mid);
updt(idx,val,2*x+1,mid+1,rx);
tree[x]=__gcd(tree[2*x+1],tree[2*x]);
return ;
}
void updt(int idx,int val){
updt(idx,val,1,0,sz-1);
}
void updt2(int idx,int val,int x,int lx,int rx){
///cout<<lx<<' '<<rx<<'\n';
if(rx<idx||lx>idx)return ;
if(lx==rx){
tree[x]*=val;
tree[x]%=(int)1e9+7ll;
return ;
}
int mid=(lx+rx)/2;
updt2(idx,val,2*x,lx,mid);
updt2(idx,val,2*x+1,mid+1,rx);
tree[x]=__gcd(tree[2*x+1],tree[2*x]);
return ;
}
void updt2(int idx,int val){
updt2(idx,val,1,0,sz-1);
}
/**int query(int l,int r,int x,int lx,int rx){
///cout<<lx<<' '<<rx<<'\n';
if(rx<l||lx>r)return 0;
if(lx>=l&&rx<=r){
return tree[x]+adr[x];
}
int mid=(lx+rx)/2;
return max(query(l,r,2*x,lx,mid),query(l,r,2*x+1,mid+1,rx))+adr[x];
}
int query(int l,int r){
return query(l,r,1,0,sz-1);
}
int query(){
return tree[1];
}
};*/
vector<int>vis;
/**
void dfs(int cr){
vis[cr]=1;
for(int i=0;i<adj[cr].size();i++){
if(!vis[adj[cr][i]])
dfs(adj[cr][i]);
}
}*/
vector<int>path;
int mtx[2005][2005];
int n=55;
struct edge{
int l,r,id;
edge(int l,int r,int id):l(l),r(r),id(id){}
};
vector<int>del;
vector<vector< edge > >adj;
void euler(int cr){
for(int i=0;i<adj[cr].size();i++){
edge cre=adj[cr][i];
if(!del[cre.id]){
del[cre.id]=1;
euler(cre.r);
}
}
path.push_back(cr);
return;
}
vector<vector<int> >rods;
vector<int>lsts;
void findrd(int cr){
///cout<<cr<<'\n';
int l=cr,r=lsts[cr];
vector<int>rod;
for(int i=l;i<r;i++){
if(rod.empty()||path[i]!=rod.back())
rod.push_back(path[i]);
if(lsts[i]<r&&lsts[i]!=-1){
findrd(i);
i=lsts[i]-1;
}
}
rods.push_back(rod);
}
int32_t main()
{
int t=1;
///cin>>t;
int cnt=1;
while(t--){
///cout<<"Case #"<<cnt<<'\n';
cnt++;
int m;
cin>>n>>m;
vector<int>occ(n+5);
int frst=-1;
memset(mtx,0,sizeof(mtx));
del=vector<int>(m+5);
adj.resize(n+5);
for(int i=0;i<m;i++){
int x,y;
cin>>x>>y;
occ[x]++; occ[y]++;
adj[x].push_back(edge(x,y,i+1));
adj[y].push_back(edge(y,x,i+1));
}
euler(1);
lsts=vector<int>(path.size(),-1);
vector<int>lsts2(n+5,-1);
/**for(int i=0;i<path.size();i++)
cout<<path[i]<<' ';
cout<<'\n';*/
for(int i=path.size()-1;i>=0;i--){
lsts[i]=lsts2[path[i]];
lsts2[path[i]]=i;
}
/**for(int i=0;i<path.size();i++)
cout<<lsts[i]<<' ';
cout<<'\n';*/
for(int i=0;i<path.size();i++){
if(lsts[i]!=-1){
findrd(i);
i=lsts[i]-1;
}
}
for(int i=0;i<rods.size();i++){
for(int j=0;j<rods[i].size();j++)
cout<<rods[i][j]<<' ';
cout<<'\n';
}
}
return 0;
}
/**
1
8 2
abczzzzz
*/
Compilation message
postmen.cpp:70:5: warning: "/*" within comment [-Wcomment]
70 | /**int query(int l,int r,int x,int lx,int rx){
|
postmen.cpp: In function 'void euler(long long int)':
postmen.cpp:123:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
123 | for(int i=0;i<adj[cr].size();i++){
| ~^~~~~~~~~~~~~~~
postmen.cpp: In function 'int32_t main()':
postmen.cpp:190:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
190 | for(int i=0;i<path.size();i++){
| ~^~~~~~~~~~~~
postmen.cpp:196:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
196 | for(int i=0;i<rods.size();i++){
| ~^~~~~~~~~~~~
postmen.cpp:197:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
197 | for(int j=0;j<rods[i].size();j++)
| ~^~~~~~~~~~~~~~~
postmen.cpp:166:13: warning: unused variable 'frst' [-Wunused-variable]
166 | int frst=-1;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
31724 KB |
Output is correct |
| 2 |
Correct |
18 ms |
31852 KB |
Output is correct |
| 3 |
Correct |
18 ms |
31724 KB |
Output is correct |
| 4 |
Correct |
25 ms |
32364 KB |
Output is correct |
| 5 |
Correct |
19 ms |
31980 KB |
Output is correct |
| 6 |
Correct |
22 ms |
32620 KB |
Output is correct |
| 7 |
Correct |
39 ms |
34668 KB |
Output is correct |
| 8 |
Correct |
19 ms |
32236 KB |
Output is correct |
| 9 |
Correct |
283 ms |
47328 KB |
Output is correct |
| 10 |
Correct |
21 ms |
32236 KB |
Output is correct |
| 11 |
Correct |
20 ms |
32364 KB |
Output is correct |
| 12 |
Correct |
161 ms |
48232 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
31724 KB |
Output is correct |
| 2 |
Correct |
18 ms |
31852 KB |
Output is correct |
| 3 |
Correct |
17 ms |
31724 KB |
Output is correct |
| 4 |
Correct |
27 ms |
32364 KB |
Output is correct |
| 5 |
Correct |
19 ms |
31980 KB |
Output is correct |
| 6 |
Correct |
22 ms |
32620 KB |
Output is correct |
| 7 |
Correct |
36 ms |
34668 KB |
Output is correct |
| 8 |
Correct |
20 ms |
32236 KB |
Output is correct |
| 9 |
Correct |
280 ms |
47492 KB |
Output is correct |
| 10 |
Correct |
21 ms |
32236 KB |
Output is correct |
| 11 |
Correct |
21 ms |
32364 KB |
Output is correct |
| 12 |
Correct |
158 ms |
48232 KB |
Output is correct |
| 13 |
Correct |
150 ms |
53732 KB |
Output is correct |
| 14 |
Correct |
148 ms |
50528 KB |
Output is correct |
| 15 |
Execution timed out |
1056 ms |
46488 KB |
Time limit exceeded |
| 16 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
31724 KB |
Output is correct |
| 2 |
Correct |
18 ms |
31852 KB |
Output is correct |
| 3 |
Correct |
18 ms |
31724 KB |
Output is correct |
| 4 |
Correct |
27 ms |
32364 KB |
Output is correct |
| 5 |
Correct |
19 ms |
31980 KB |
Output is correct |
| 6 |
Correct |
22 ms |
32620 KB |
Output is correct |
| 7 |
Correct |
36 ms |
34668 KB |
Output is correct |
| 8 |
Correct |
20 ms |
32364 KB |
Output is correct |
| 9 |
Correct |
287 ms |
47360 KB |
Output is correct |
| 10 |
Correct |
21 ms |
32236 KB |
Output is correct |
| 11 |
Correct |
23 ms |
32364 KB |
Output is correct |
| 12 |
Correct |
185 ms |
48232 KB |
Output is correct |
| 13 |
Correct |
149 ms |
53732 KB |
Output is correct |
| 14 |
Correct |
146 ms |
50528 KB |
Output is correct |
| 15 |
Execution timed out |
1057 ms |
46616 KB |
Time limit exceeded |
| 16 |
Halted |
0 ms |
0 KB |
- |
