Submission #226520

#	Time	Username	Problem	Language	Result	Execution time	Memory
226520		MKopchev	Senior Postmen (BOI14_postmen)	C++14	100 / 100	499 ms	61816 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];

int outp[nmax],pnt=0;

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);
        }
    pnt++;
    outp[pnt]=node;
}

int current[nmax],pnt_current=0;

int lst_seen[nmax];

void add(int val)
{
    pnt_current++;
    lst_seen[val]=pnt_current;
    current[pnt_current]=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));

    //for(int i=1;i<=pnt;i++)cout<<outp[i]<<" ";cout<<endl;

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

        vector<int> help={};
        int pos=i;

        while(current[pnt_current]!=outp[i])
        {
            printf("%i ",current[pnt_current]);
            lst_seen[current[pnt_current]]=-1;
            pnt_current--;
        }

        printf("%i",current[pnt_current]);
        lst_seen[current[pnt_current]]=-1;
        pnt_current--;

        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:65:13: warning: unused variable 'pos' [-Wunused-variable]
         int pos=i;
             ^~~
postmen.cpp:40: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:45: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: 45 / 45