제출 #47356

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
47356		dqhungdl	관광 (NOI14_sightseeing)	C++17	15 / 25	3542 ms	64256 KiB

sightseeing

#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';
    }
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 4
• Subtask 2: 5 / 5
• Subtask 3: 6 / 6
• Subtask 4: 0 / 10