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>
/**
|||||||||| ||||| ||||| ||||||||||
||||||||||||| ||||| ||||| |||||
|||| |||||| ||||| ||||| |||||
||||||||||||||||| ||||||||||||||| ||||||||||
||||||||||||||||||| ||||||||||||||| |||||
||||| ||||| ||||| ||||| |||||
||||| ||||| ||||| ||||| ||||||||||
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<vector<int> >adj;
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;
void euler(int cr){
for(int i=0;i<n+5;i++){
if(mtx[cr][i]&&cr!=i){
mtx[cr][i]--;
mtx[i][cr]--;
euler(i);
}
}
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));
for(int i=0;i<m;i++){
int x,y;
cin>>x>>y;
occ[x]++; occ[y]++;
mtx[x][y]++;
mtx[y][x]++;
}
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 (stderr)
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 dfs(long long int)':
postmen.cpp:102:18: 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]
102 | for(int i=0;i<adj[cr].size();i++){
| ~^~~~~~~~~~~~~~~
postmen.cpp: In function 'int32_t main()':
postmen.cpp:178: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]
178 | for(int i=0;i<path.size();i++){
| ~^~~~~~~~~~~~
postmen.cpp:184: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]
184 | for(int i=0;i<rods.size();i++){
| ~^~~~~~~~~~~~
postmen.cpp:185: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]
185 | for(int j=0;j<rods[i].size();j++)
| ~^~~~~~~~~~~~~~~
postmen.cpp:156:13: warning: unused variable 'frst' [-Wunused-variable]
156 | int frst=-1;
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |