oj.uz

Submission #29488

# Submission time Handle Problem Language Result Execution time Memory
29488 2017-07-19T13:20:22 Z samir_droubi Sightseeing (NOI14_sightseeing) C++14
25 / 25
 2923 ms 167140 KB 
#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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19600 KB Output is correct
2 Correct 3 ms 19600 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19772 KB Output is correct
2 Correct 6 ms 19600 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 22192 KB Output is correct
2 Correct 23 ms 22116 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2276 ms 93412 KB Output is correct
2 Correct 2923 ms 167140 KB Output is correct