Submission #1300678

#TimeUsernameProblemLanguageResultExecution timeMemory
1300678danglayloi1Roadside Advertisements (NOI17_roadsideadverts)C++20
100 / 100
37 ms11524 KiB
#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
using ll = long long;
const ll mod=1e9+7;
const int nx=5e4+5;
const int LG=18;
int n, q, a[nx], h[nx], up[nx][LG], dep[nx], st[nx], tim=0, en[nx];
vector<ii> adj[nx];
bool ok[nx];
void dfs(int u)
{
    st[u]=++tim;
    for(auto it:adj[u])
    {
        int v, w;
        tie(v, w)=it;
        if(v==up[u][0]) continue;
        up[v][0]=u;
        h[v]=h[u]+1;
        dep[v]=dep[u]+w;
        for(int i = 1; i < LG; i++)
            up[v][i]=up[up[v][i-1]][i-1];
        dfs(v);
    }
    en[u]=tim;
}
bool cmp(int x, int y)
{
    return st[x]<st[y];
}
int jump(int u, int k)
{
    for(int i = 0; i < LG; i++)
        if(k>>i&1) u=up[u][i];
    return u;
}
int lca(int u, int v)
{
    if(h[u]<h[v]) swap(u, v);
    u=jump(u, h[u]-h[v]);
    if(u==v) return u;
    for(int i = LG-1; i >= 0; i--)
        if(up[u][i]!=up[v][i])
            u=up[u][i], v=up[v][i];
    return up[u][0];
}
stack<int> f;
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i = 1; i < n; i++)
    {
        int u, v, w;
        cin>>u>>v>>w;
        u++, v++;
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
    dfs(1);
    cin>>q;
    while(q--)
    {
        int k=5, ans=0;
        for(int i = 1; i <= k; i++)
            cin>>a[i], a[i]++, ok[a[i]]=1;
        sort(a+1, a+k+1, cmp);
        for(int i = 1; i < k; i++)
        {
            int p=lca(a[i], a[i+1]);
            if(!ok[p])
            {
                ok[p]=1;
                a[++k]=p;
            }
        }
        sort(a+1, a+k+1, cmp);
        while(f.size()) f.pop();
        f.push(a[1]);
        for(int i = 2; i <= k; i++)
        {
            while(f.size() && en[f.top()]<en[a[i]]) f.pop();
            ans+=dep[a[i]]-dep[f.top()];
            f.push(a[i]);
        }
        cout<<ans<<'\n';
        for(int i = 1; i <= k; i++)
            ok[a[i]]=0;
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...