oj.uz

Submission #12678

# Submission time Handle Problem Language Result Execution time Memory
12678 2014-12-28T16:33:05 Z dohyun0324 Sightseeing (NOI14_sightseeing) C++
25 / 25
 2356 ms 148428 KB 
#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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 132852 KB Output is correct
2 Correct 0 ms 132852 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 132852 KB Output is correct
2 Correct 4 ms 132852 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 133908 KB Output is correct
2 Correct 20 ms 133776 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1580 ms 144204 KB Output is correct
2 Correct 2356 ms 148428 KB Output is correct