Submission #374577

#	Time	Username	Problem	Language	Result	Execution time	Memory
374577		Ahmad_Hasan	Senior Postmen (BOI14_postmen)	C++17	38 / 100	1091 ms	15240 KiB

postmen

#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;
        }
    }
    for(int i=0;i<rod.size();i++)
        cout<<rod[i]<<' ';
    cout<<'\n';

}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);      cout.tie(0);
    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 (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 euler(int)':
postmen.cpp:123:18: warning: comparison of integer expressions of different signedness: '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 'void findrd(int)':
postmen.cpp:149:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |     for(int i=0;i<rod.size();i++)
      |                 ~^~~~~~~~~~~
postmen.cpp: In function 'int32_t main()':
postmen.cpp:194:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  194 |         for(int i=0;i<path.size();i++){
      |                     ~^~~~~~~~~~~~
postmen.cpp:170:13: warning: unused variable 'frst' [-Wunused-variable]
  170 |         int frst=-1;
      |             ^~~~

• Subtask 1: 38 / 38
• Subtask 2: 0 / 17
• Subtask 3: 0 / 45