Submission #10721

#	Time	Username	Problem	Language	Result	Execution time	Memory
10721		dohyun0324	Senior Postmen (BOI14_postmen)	C++98	100 / 100	420 ms	46720 KiB

postmen

#include<stdio.h>
#include<algorithm>
using namespace std;
int p,n,m,pos[500010],chv[500010],dap[500010],top,cnt,w,che[500010];
struct data
{
    int x,y,z;
    bool operator<(const data&r)const
    {
        return x<r.x;
    }
}arr[1000010];
void dfs(int x)
{
    int i,j;
    chv[x]=cnt;
    for(i=pos[x];;i++)
    {
        if(p)
        {
            dap[++top]=x;
            if(x==p)
            {
                for(j=1;j<=top;j++) printf("%d ",dap[j]);
                printf("\n");
                p=0;
            }
            else
            {
                chv[x]=0;
                break;
            }
        }
        if(arr[i].x!=x) break;
        if(che[arr[i].z]) continue;
        che[arr[i].z]=1;
        if(chv[arr[i].y]==cnt)
        {
            p=arr[i].y;
            top=0;
            dap[++top]=x;
            i++;
            chv[x]=0;
            break;
        }
        dfs(arr[i].y);
    }
    pos[x]=i;
}
int main()
{
    int i,j,x,y;
    scanf("%d %d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d %d",&x,&y);
        w++; arr[w].x=x; arr[w].y=y; arr[w].z=i;
        w++; arr[w].x=y; arr[w].y=x; arr[w].z=i;
    }
    sort(arr+1,arr+w+1);
    for(i=1;i<=w;i++)
    {
        if(arr[i].x!=arr[i-1].x) pos[arr[i].x]=i;
    }
    for(i=1;i<=n;i++)
    {
        while(arr[pos[i]].x==i)
        {
            p=0; cnt++; dfs(i);
        }
    }
    return 0;
}

Compilation message (stderr)

postmen.cpp: In function 'int main()':
postmen.cpp:52:11: warning: unused variable 'j' [-Wunused-variable]
     int i,j,x,y;
           ^
postmen.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~~
postmen.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&x,&y);
         ~~~~~^~~~~~~~~~~~~~~

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