/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 3ms 6.527 MiB
#2 Accepted 3ms 4.527 MiB
#3 Accepted 3ms 8.527 MiB
#4 Accepted 3ms 6.547 MiB
#5 Accepted 4ms 6.527 MiB
#6 Accepted 4ms 6.531 MiB
#7 Wrong Answer 15ms 6.812 MiB
#8 Wrong Answer 16ms 6.785 MiB

Code

/*
 *   Copyright (c) 2024 Emon Thakur
 *   All rights reserved.
 */
#include<bits/stdc++.h>
using namespace std;
int heavy[100005],height[100005],nodes,parent[100005],a[100005],dp[100005][20];
vector<pair<int,int>> g[100005];

int heavychild(int node,int par)
{
    parent[node] = par;
    int mx=0,tot=0,hc=0;
    for(pair<int,int> e:g[node])
    {
        if(e.first==par) continue;
        a[e.first] =  e.second;
        nodes = heavychild(e.first,node);
        tot += nodes;
        if(nodes > mx) mx=nodes, hc=e.first;
    }
    heavy[node] = hc;
    return tot+1;
}

void binarylifting(int node,int par,int h)
{
    height[node] = h;
    dp[node][0] = par;
    for(int i=1;i<20;i++) dp[node][i] = dp[dp[node][i-1]][i-1];
    for(pair<int,int>  e:g[node])
    {
        if(e.first == par) continue;
        binarylifting(e.first,node,h+1);
    }
}

int kthparent(int v,int k)
{
    for(int i=19;i>=0;i--)
    {
        if(k & (1<<i)) v = dp[v][i];
    }
    return v;
}

int lca(int u,int v)
{
    if(height[u] > height[v]) swap(u,v);
    v = kthparent(v , abs(height[u]-height[v]));
    if(u==v) return u;
    for(int i=19;i>=0;i--)
    {
        if(dp[u][i] == dp[v][i]) continue;
        u = dp[u][i];
        v = dp[v][i];
    }
    return dp[u][0];
}

int pos[100005],v[100005],head[100005],indx=0;
void HLD(int node,int par, int hd)
{
    pos[node] = indx;
    v[indx++] = a[node];
    head[node] =  hd;
    for(pair<int,int> e:g[node])
    {
        if(e.first == par) continue;
        if(e.first == heavy[node]) HLD(e.first , node, hd);
        else HLD(e.first , node , e.first);
    }
}

int sg[800005];
void buildsg(int node,int start,int end)
{
    if(start==end)
    {
        sg[node] = v[start];
        return;
    }
    int mid = (start+end)/2;
    buildsg(node*2,start,mid);
    buildsg(node*2+1,mid+1,end);
    sg[node] = max(sg[node*2] , sg[node*2+1]);
}

int sgquery(int node,int start,int end,int l,int r)
{
    if(l>end || r<start) return 0;
    if(l<=start && r>=end) return sg[node];
    int mid = (start+end)/2;
    return max(sgquery(node*2,start,mid,l,r) , sgquery(node*2+1,mid+1,end,l,r));
}


int queryup(int u,int lc)
{
    int ans = 0;
    while(head[u] != head[lc])
    {
        ans = max(ans , sgquery(1,0,indx-1,pos[head[u]],pos[u]));
        u = parent[head[u]];
    }
    return max(ans , sgquery(1,0,indx-1,pos[lc],pos[u]));
}

int query(int u,int v)
{
    int lc = lca(u,v);
    int d = abs(height[lc]-height[u]);
    int ans = 0;
    if(d) 
    {
        int lc1 = kthparent(u,d-1);
        ans = max(ans,queryup(u,lc1));
    } 
    d = abs(height[lc]-height[v]);
    if(d)
    {
        int lc2 = kthparent(v,d-1);
        ans = max(ans , queryup(v,lc2));
    }
    return ans;
}

int main()
{
    int n,q; cin >> n >> q;
    for(int i=0;i<n-1;i++)
    {
        int u,v,w; cin >> u >> v >> w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    heavychild(1,0);
    binarylifting(1,0,0);
    HLD(1,0,1);
    buildsg(1,0,indx-1);
    while(q--)
    {
        int a,b; cin >> a >> b;
        cout<<query(a,b)<<endl;
    }
}

Information

Submit By
Type
Submission
Problem
P1019 Graph Stuff
Language
C++17 (G++ 13.2.0)
Submit At
2024-11-03 09:20:42
Judged At
2024-11-03 09:20:42
Judged By
Score
5
Total Time
16ms
Peak Memory
8.527 MiB