Submission #936438

#	Time	Username	Problem	Language	Result	Execution time	Memory
936438		HorizonWest	Cat Exercise (JOI23_ho_t4)	C++17	0 / 100	11 ms	45660 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) 
{ 
    for(int j=1; j<22; j++) 
        bl[j][node]=bl[j-1][bl[j-1][node]]; 
    for(auto i:G[node]) 
        if(v[i]==0){ 
            v[i]=v[node]+1; 
            bl[0][i]=node; 
            dfs(i); 
        }        
} 
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; 
      	a = cad[a-1].first;
      	b = cad[b-1].first;
        if(a < b) swap(a,b); 
        g[a].push_back(b); 
        G[a].push_back(b); 
        G[b].push_back(a); 
    } 
    dfs(1); 
    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<<sol[cad[n-1].second]; 
}

Compilation message (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: 0 / 7
• Subtask 2: 0 / 7
• Subtask 3: 0 / 7
• Subtask 4: 0 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 23
• Subtask 7: 0 / 26