Submission #1203462

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203462		vicvic	Roadside Advertisements (NOI17_roadsideadverts)	C++20	100 / 100	159 ms	23100 KiB

roadsideadverts

#include <bits/stdc++.h>
#define int long long
using namespace std;
ifstream f ("test.in");
ofstream g ("test.out");
const int NMAX=1e5, LGMAX=17;
vector <pair <int, int>> vec[NMAX+5];
int n;
int t[NMAX+5][LGMAX+2], sum[NMAX+5][LGMAX+2], v[NMAX+5], depth[NMAX+5];
void dfs (int nod, int tatal=0, int w=0)
{
    t[nod][0]=tatal;
    depth[nod]=depth[tatal]+1;
    sum[nod][0]=w;
    for (int i=1;i<=LGMAX;i++)
    {
        t[nod][i]=t[t[nod][i-1]][i-1];
        sum[nod][i]=sum[nod][i-1]+sum[t[nod][i-1]][i-1];
    }
    for (auto adj : vec[nod])
    {
        if (adj.first==tatal)
            continue;
        dfs (adj.first, nod, adj.second);
    }
}
pair <int, int> LCA (int x, int y)
{
    if (x==y)
        return {x, 0};
    int cost=0;
    if (depth[x]>depth[y])
        swap (x, y);
    for (int i=LGMAX;i>=0;i--)
        if (t[y][i]!=0 && depth[t[y][i]]>=depth[x])
            cost+=sum[y][i], y=t[y][i];
    if (x==y)
        return {x, cost};
    for (int i=LGMAX;i>=0;i--)
        if (t[y][i]!=0 && t[y][i]!=t[x][i])
            cost+=sum[x][i], cost+=sum[y][i], x=t[x][i], y=t[y][i];
    return {t[x][0], cost+t[x][0]+t[y][0]};
}
int32_t main ()
{
    ios_base :: sync_with_stdio (0);
    cin.tie (nullptr);
    cin >> n;
    for (int i=1;i<n;i++)
    {
        int x, y, w;
        cin >> x >> y >> w;
        x++;
        y++;
        vec[x].push_back ({y, w});
        vec[y].push_back ({x, w});
    }
    dfs (1);
    int q;
    cin >> q;
    while (q--)
    {
        int glob_lca=0;
        for (int i=0;i<5;i++)
        {
            cin >> v[i];
            v[i]++;
            glob_lca=(glob_lca==0?v[i]:LCA (glob_lca, v[i]).first);
        }
        int cost=0;
        for (int msk=1;msk<(1 << 5);msk++)
        {
            int crt_lca=0;
            for (int i=0;i<5;i++)
            {
                if (msk & (1 << i))
                    crt_lca=(crt_lca==0?v[i]:LCA (crt_lca, v[i]).first);
            }
            cost+=LCA (crt_lca, glob_lca).second*(__builtin_popcount (msk)%2==0?-1:1);
        }
        cout << cost << "\n";
    }
    return 0;
}

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