Submission #12678

#	Time	Username	Problem	Language	Result	Execution time	Memory
12678		dohyun0324	Sightseeing (NOI14_sightseeing)	C++98	25 / 25	2356 ms	148428 KiB

sightseeing

#include<stdio.h>
#include<list>
using namespace std;
list<int>l[500010];
list<int>::iterator p;
int n,m,q,k,cnt[200010],x[5000010],y[5000010],c[5000010],group[500010],ord[500010],dap[500010];
struct data
{
    int x,y,c;
}a[5000010];
int up(int x)
{
    if(x==group[x]) return x;
    return group[x]=up(group[x]);
}
int main()
{
    int i,j;
    scanf("%d %d %d",&n,&m,&q);
    for(i=1;i<=m;i++){
        scanf("%d %d %d",&x[i],&y[i],&c[i]);
        cnt[c[i]]++;
    }
    for(i=1;i<=200000;i++) cnt[i]+=cnt[i-1];
    for(i=1;i<=m;i++)
    {
        cnt[c[i]-1]++;
        a[cnt[c[i]-1]].x=x[i];
        a[cnt[c[i]-1]].y=y[i];
        a[cnt[c[i]-1]].c=c[i];
    }
    for(i=1;i<=m;i++) x[i]=a[i].x, y[i]=a[i].y, c[i]=a[i].c;
    for(i=1;i<=n;i++)
    {
        group[i]=i;
        l[i].push_back(i);
    }
    for(i=m;i>=1;i--)
    {
        x[i]=up(x[i]); y[i]=up(y[i]);
        if(x[i]==y[i]) continue;
        if(up(1)==x[i])
        {
            p=l[y[i]].begin();
            while(p!=l[y[i]].end()){
                dap[*p]=c[i];
                p++;
            }
        }
        if(up(1)==y[i])
        {
            p=l[x[i]].begin();
            while(p!=l[x[i]].end()){
                dap[*p]=c[i];
                p++;
            }
        }
        if(ord[x[i]]>ord[y[i]]){
            group[y[i]]=x[i];
            l[x[i]].splice(l[x[i]].end(),l[y[i]]);
        }
        else if(ord[x[i]]<ord[y[i]]){
            group[x[i]]=y[i];
            l[y[i]].splice(l[y[i]].end(),l[x[i]]);
        }
        else
        {
            group[y[i]]=x[i];
            l[x[i]].splice(l[x[i]].end(),l[y[i]]);
            ord[x[i]]++;
        }
    }
    for(i=1;i<=q;i++)
    {
        scanf("%d",&k);
        printf("%d\n",dap[k]);
    }
    return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 6 / 6
• Subtask 4: 10 / 10