Submission #752600

#	Time	Username	Problem	Language	Result	Execution time	Memory
752600		12345678	Roadside Advertisements (NOI17_roadsideadverts)	C++17	100 / 100	84 ms	11120 KiB

roadsideadverts

#include <bits/stdc++.h>

using namespace std;

const int nx=5e4+5, lx=17;
int n, u, v, w, pa[nx][lx], lvl[nx], ds[nx], l[6], q, tn;
vector<vector<pair<int, int>>> d(nx);

void dfs(int u, int p)
{
    lvl[u]=lvl[p]+1;
    pa[u][0]=p;
    for (int i=1; i<lx; i++) pa[u][i]=pa[pa[u][i-1]][i-1];
    for (auto [v, w]:d[u]) if (v!=p) ds[v]=ds[u]+w, dfs(v, u);
}

int lca(int u, int v)
{
    if (lvl[u]>lvl[v]) swap(u, v);
    for (int i=lx-1; i>=0; i--) if (lvl[pa[v][i]]>=lvl[u]) v=pa[v][i];
    if (u==v) return v;
    for (int i=lx-1; i>=0; i--) if (pa[u][i]!=pa[v][i]) u=pa[u][i], v=pa[v][i];
    return pa[u][0];
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n; lvl[n]=1e9;
    for (int i=0; i<n-1; i++) cin>>u>>v>>w, d[u].push_back({v, w}), d[v].push_back({u, w});
    dfs(0, 0);
    cin>>q;
    while (q--)
    {
        for (int i=0; i<5; i++) cin>>l[i];
        int tn=n, ans=0;
        for (int i=1; i<5; i++)
        {
            int cn=lca(l[0], l[i]);
            if (lvl[cn]<lvl[tn]) tn=cn;
        }
        for (int i=0; i<5; i++)
        {
            int mn=ds[l[i]]-ds[tn];
            for (int j=0; j<i; j++) mn=min(mn, ds[l[i]]-ds[lca(l[i], l[j])]);
            ans+=mn;
        }
        cout<<ans<<'\n';
    }
}

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 40 / 40
• Subtask 4: 30 / 30