Submission #226516

#	Time	Username	Problem	Language	Result	Execution time	Memory
226516		MKopchev	Senior Postmen (BOI14_postmen)	C++14	55 / 100	503 ms	63812 KiB

postmen

#include<bits/stdc++.h>
using namespace std;

const int nmax=5e5+42;

int n,m;

vector< pair<int,int> > adj[nmax];

int pointer[nmax];

vector<int> outp;

bool blocked[nmax];

void tour(int node)
{
    for(;pointer[node]<adj[node].size();pointer[node]++)
        if(blocked[adj[node][pointer[node]].second]==0)
        {
            blocked[adj[node][pointer[node]].second]=1;
            tour(adj[node][pointer[node]].first);
        }
    outp.push_back(node);
}

vector<int> current;

int lst_seen[nmax];

void add(int val)
{
    lst_seen[val]=current.size();
    current.push_back(val);
}
int main()
{
    scanf("%i%i",&n,&m);

    for(int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%i%i",&u,&v);
        adj[u].push_back({v,i});
        adj[v].push_back({u,i});
    }

    tour(1);

    memset(lst_seen,-1,sizeof(lst_seen));

    /*
    cout<<outp.size()<<endl;
    for(auto k:outp)cout<<k<<" ";cout<<endl;
    */

    for(int i=0;i<outp.size();i++)
    {
        if(lst_seen[outp[i]]==-1)
        {
            add(outp[i]);
            continue;
        }

        vector<int> help={};
        int pos=i;
        while(current.back()!=outp[i])
        {
            help.push_back(current.back());
            lst_seen[current.back()]=-1;
            current.pop_back();
        }

        help.push_back(current.back());
        lst_seen[current.back()]=-1;
        current.pop_back();

        //cout<<"i= "<<i<<" -> ";

        for(auto k:help)
            printf("%i ",k);
        printf("\n");

        add(outp[i]);
    }
    return 0;
}

Compilation message (stderr)

postmen.cpp: In function 'void tour(int)':
postmen.cpp:18:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(;pointer[node]<adj[node].size();pointer[node]++)
          ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
postmen.cpp: In function 'int main()':
postmen.cpp:57:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<outp.size();i++)
                 ~^~~~~~~~~~~~
postmen.cpp:66:13: warning: unused variable 'pos' [-Wunused-variable]
         int pos=i;
             ^~~
postmen.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i",&n,&m);
     ~~~~~^~~~~~~~~~~~~~
postmen.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i%i",&u,&v);
         ~~~~~^~~~~~~~~~~~~~

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