Submission #29488

#	Time	Username	Problem	Language	Result	Execution time	Memory
29488		samir_droubi	Sightseeing (NOI14_sightseeing)	C++14	25 / 25	2923 ms	167140 KiB

sightseeing

#include <bits/stdc++.h>
using namespace std;
int n,m,q;
vector<pair<int,pair<int,int> > >e;
const int mxn=(5e5)+5;
int p[mxn];
int sz[mxn];
vector<int>com[mxn];
int ans[mxn];
int mn=(1e9);
int find(int v)
{
    if(v==p[v])return v;
    return p[v]=find(p[v]);
}
void merge(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x==y)return;
    if(find(1)==x && ans[y]==-1)
    {
        for(int i=0;i<sz[y];++i)
            ans[com[y][i]]=mn;
    }
    if(find(1)==y && ans[x]==-1)
    {
        for(int i=0;i<sz[x];++i)
            ans[com[x][i]]=mn;
    }
    if(sz[x]>sz[y])swap(x,y);
    sz[y]+=sz[x];
    p[x]=y;
    for(int i=0;i<sz[x];++i)
        com[y].push_back(com[x][i]);
    com[x].clear();
    sz[x]=0;
}
int main()
{
    scanf("%d%d%d",&n,&m,&q);
    memset(ans,-1,sizeof ans);
    for(int i=1;i<=m;++i)
    {
        int x,y,w;
        scanf("%d%d%d",&x,&y,&w);
        e.push_back({w,{x,y}});
    }
    for(int i=1;i<=n;++i)
    {
        sz[i]=1;
        p[i]=i;
        com[i].push_back(i);
    }
    sort(e.begin(),e.end());
    for(int i=m-1;i>=0;--i)
    {
        int w=e[i].first;
        int x=e[i].second.first;
        int y=e[i].second.second;
        mn=w;
        merge(x,y);
    }
    while(q--)
    {
        int x;
        scanf("%d",&x);
        printf("%d\n",ans[x]);
    }
    return 0;
}

Compilation message (stderr)

sightseeing.cpp: In function 'int main()':
sightseeing.cpp:41:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d",&n,&m,&q);
                             ^
sightseeing.cpp:46:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d",&x,&y,&w);
                                 ^
sightseeing.cpp:67:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&x);
                       ^

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