oj.uz

답안 #936373

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
936373 2024-03-01T18:03:28 Z Marco_Escandon Cat Exercise (JOI23_ho_t4) C++11
0 / 100
 48 ms 92240 KB 
#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];
ll 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;
        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);
    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

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++)
      |                      ~^~~~~~~~~
Main.cpp: In function 'll dfs(ll)':
Main.cpp:32:1: warning: no return statement in function returning non-void [-Wreturn-type]
   32 | }
      | ^

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 46 ms 92240 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 46 ms 92240 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 46 ms 92240 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 46 ms 92240 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 46 ms 92240 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 48 ms 92168 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 46 ms 92240 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -