Submission #936443

#	Time	Username	Problem	Language	Result	Execution time	Memory
936443		HorizonWest	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	356 ms	49108 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; 
} 

const long long Inf = 1e9 + 7;
 
struct LowerCommonAncestor
{
    vector <int> L, E, H; int idx, n;
 
    void dfs(int cur, int depth, int parent)
    {
        H[cur] = idx;
        E[idx] = cur;
        L[idx++] = depth;
 
        for (auto& u : G[cur]) if(u != parent)
        {
            dfs(u, depth + 1, cur);
            E[idx] = cur;
            L[idx++] = depth;
        }
    }
 
    vector <int> tree; int l;
 
    int query(int node, int x, int y, int s, int e)
    {
        if (x > e || y < s) return 0;
 
        if (s >= x && e <= y)
            return tree[node];
 
        int middle = (s + e) / 2;
 
        int id1 = query(node * 2, x, y, s, middle),
            id2 = query(node * 2 + 1, x, y, middle + 1, e);
 
        return (L[id1] > L[id2] ? id2 : id1);
    }
 
    int query(int i, int j) { return query(1, i, j, 1, l); }
 
    void Segment_tree(int n)
    {
        for (l = 1; l < n; l = (l << 1));
        tree.assign(2 * l, 0); L[0] = Inf;
 
        for (int i = 0; i < n; i++)
            tree[i + l] = i + 1;
 
        for (int i = l - 1; i > 0; i--)
        {
            tree[i] = (L[tree[2 * i]] > L[tree[2 * i + 1]] ?
                tree[2 * i + 1] : tree[2 * i]);
        }
    }
 
    int Ancestor(int i, int j)
    {
        int a = min(H[i], H[j]), b = max(H[i], H[j]);
        return E[query(a, b)];
    }
 
    int Dist(int x)
    {
        return L[H[x]];
    }
 
    int sol(int i, int j)
    {
        int g = Ancestor(i, j);
        return (Dist(i) + Dist(j) - (2 * Dist(g)));
    }
 
    LowerCommonAncestor(int lenght, int x)
    {
        n = lenght; idx = 1;
 
        L.assign(2 * n, -1);
        E.assign(2 * n, -1);
        H.assign(2 * n, -1);
 
        dfs(x, 0, 0); Segment_tree(2*n-2); //RMQ();
    }
};
 
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); 
    } 
    LowerCommonAncestor D(n, 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)]+D.sol(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:17:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |         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