oj.uz

Submission #47356

# Submission time Handle Problem Language Result Execution time Memory
47356 2018-05-01T07:35:22 Z dqhungdl Sightseeing (NOI14_sightseeing) C++17
15 / 25
 3500 ms 64256 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> ii;
typedef pair<int,ii> iii;
int n,m,T,d[500005],P[500005];
vector<int> S[500005];
vector<iii> Edge;

void ReadInt(int &number)
{
    number=0;
    int c=getchar();
    while(c<'0'||c>'9')
        c=getchar();
    for (;('0'<=c&&c<='9');c=getchar())
        number=number*10+c-48;
}

int Find(int u)
{
    if(u==P[u])
        return u;
    return P[u]=Find(P[u]);
}

void Union(int u,int v,int hasroot,int w)
{
    if(S[u].size()<S[v].size())
        swap(u,v);
    P[v]=u;
    while(S[v].size()>0)
    {
        S[u].push_back(S[v].back());
        S[v].pop_back();
    }
    if(hasroot==1)
        for(int i=0;i<S[u].size();i++)
            d[S[u][i]]=max(d[S[u][i]],w);
}

int main()
{
    ios_base::sync_with_stdio(false);
    //freopen("TEST.INP","r",stdin);
    ReadInt(n);
    ReadInt(m);
    ReadInt(T);
    int u,v,w;
    while(m--)
    {
        ReadInt(u);
        ReadInt(v);
        ReadInt(w);
        Edge.push_back(iii(w,ii(u,v)));
    }
    for(int i=1;i<=n;i++)
    {
        P[i]=i;
        S[i].push_back(i);
    }
    d[1]=1e9;
    sort(Edge.begin(),Edge.end(),greater<iii>());
    for(int i=0;i<Edge.size();i++)
    {
        int root=Find(1);
        int u=Find(Edge[i].second.first);
        int v=Find(Edge[i].second.second);
        if(u!=v)
            Union(u,v,(u==root||v==root),Edge[i].first);
    }
    while(T--)
    {
        ReadInt(u);
        cout<<d[u]<<'\n';
    }
}

Compilation message

sightseeing.cpp: In function 'void Union(int, int, int, int)':
sightseeing.cpp:39:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<S[u].size();i++)
                     ~^~~~~~~~~~~~
sightseeing.cpp: In function 'int main()':
sightseeing.cpp:65:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<Edge.size();i++)
                 ~^~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12152 KB Output is correct
2 Correct 12 ms 12152 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12188 KB Output is correct
2 Correct 12 ms 12188 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 723 ms 14912 KB Output is correct
2 Correct 605 ms 14912 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3542 ms 64256 KB Time limit exceeded
2 Halted 0 ms 0 KB -