제출 #936464

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
936464		Marco_Escandon	Cat Exercise (JOI23_ho_t4)	C++11	100 / 100	491 ms	76116 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct DSUF{
    vector<ll> P;
    ll fs(ll node){
        if(P[node]==node) return node;
        return P[node]=fs(P[node]);
    }
    void us(ll a, ll b){
        a=fs(a);b=fs(b);
        if(a!=b) P[b]=a;
    }
    DSUF(ll n){
        P.assign(n+5,0);
        for(int i=0; i<P.size(); i++)
            P[i]=i;
    }
};
vector<ll> g[200001], v(200001,0),G[200001];
ll bl[22][200001];
void dfs(ll node,ll padre, ll p)
{
    bl[0][node]=padre; v[node]=p;
    for(int i=1; i<22; i++)
        bl[i][node]=bl[i-1][bl[i-1][node]];
    for(auto i:G[node])
        if(padre!=i)
            dfs(i,node,p+1);
}
ll cost(ll a, ll b)
{
    if(v[a]<v[b])
        swap(a,b);
    ll cost=v[a]-v[b];
    for(int i=21; i>-1; i--)
        if((cost&(1<<i))!=0)
            a=bl[i][a];
    for(int i=21; i>-1; i--)
    {
        if(bl[i][a]!=bl[i][b])
        {
            a=bl[i][a];
            b=bl[i][b];
            cost+=(1<<i)*2;
        }
    }
    if(a!=b) cost+=2;
    return cost;
}
int main()
{
    ll n;
    cin>>n;
    pair<ll,ll> cad[n];
    DSUF asd(n+2);
    for(int i=0; i<n; i++)
    {
        cin>>cad[i].first;
        cad[i].second=i+1;
    }
    for(int i=0; i<n-1; i++)
    {
        ll a,b;
        cin>>a>>b;
        if(cad[a-1].first<cad[b-1].first) swap(a,b);
        g[a].push_back(b);
        G[a].push_back(b);
        G[b].push_back(a);
    }
    dfs(1,0,0);
    sort(cad,cad+n);
    ll sol[n+2]={ };
    for(int i=0; i<n; i++)
    {
        pair<ll,ll> temp=cad[i];
        for(auto i:g[temp.second])
        {
            sol[temp.second]=max(sol[temp.second],sol[asd.fs(i)]+cost(temp.second,asd.fs(i)));
            asd.us(temp.second,i);
        }
        //cout<<temp.second<<sol[temp.second]<<" ";
    }
    cout<<sol[cad[n-1].second];
}

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

Main.cpp: In constructor 'DSUF::DSUF(ll)':
Main.cpp:16:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |         for(int i=0; i<P.size(); i++)
      |                      ~^~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 23 / 23
• Subtask 7: 26 / 26