Submission #765767

#	Time	Username	Problem	Language	Result	Execution time	Memory
765767		vjudge1	Roadside Advertisements (NOI17_roadsideadverts)	C++17	7 / 100	105 ms	21268 KiB

roadsideadverts

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")

#include <bits/stdc++.h>

#define ll long long
#define fi first
#define se second
#define pb push_back
#define sz size
#define iosBASE ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define Freopen freopen ("input.txt", "r", stdin);freopen ("output.txt", "w", stdout);

using namespace std;

// const ll K = 32;    
const ll INF = 1e18;
const ll mod = 1e9 + 7;
const ll N = 1e5 + 5;

int n, q;
int p[50005][20], sum[50005][20], l[50005];;
vector <int> g[50005];
map <pair <int, int>, int> mp;

void dfs (int v, int pr)
{
    l[v] = l[pr] + 1;
    for (int bit = 1; bit < 20; bit++)
    {
        p[v][bit] = p[p[v][bit - 1]][bit - 1];
        sum[v][bit] = sum[v][bit - 1] + sum[p[v][bit - 1]][bit - 1];
    }
    for (int to : g[v])
    {
        if (to == pr) continue;
        sum[to][0] = mp[{v, to}];
        p[to][0] = v;
        dfs (to, v);
    }
}

pair <int, int> get (int a, int x)
{
    int sumres = 0;
    for (int bit = 0; bit < 20; bit++)
    {
        if ((x & (1 << bit)) > 0)
        {
            sumres += sum[a][bit];
            a = p[a][bit];
        }
    }
    return {a, sumres};
}

pair <int, int> lca (int a, int b)
{
    int sumres = 0;
    pair <int, int> gt;
    if (l[a] > l[b])
    {
        gt = get (a, l[a] - l[b]);
        a = gt.fi;
        sumres = gt.se;
    }
    b = get (b, l[b] - l[a]).fi;
    if (a == b) return {l[a], sumres};
    for (int bit = 19; bit >= 0; bit--)
    {
        if (p[a][bit] != p[b][bit] || bit == 0)
        {
            sumres += sum[a][bit];
            a = p[a][bit];
            b = p[b][bit];
        }
    }
    return {l[a], sumres};
}
    
void ma1n ()
{
    cin >> n;
    for (int i = 1, u, v, w; i < n; i++)
    {
        cin >> u >> v >> w;
        u++;
        v++;
        g[u].pb (v);
        g[v].pb (u);
        mp[{u, v}] = mp[{v, u}] = w;
    }
    dfs (1, 1);
    cin >> q;
    int a[10];
    for (int t = 1; t <= q; t++)
    {
        int ans = 0;
        pair <int, int> pr = {0, 100000};
        for (int i = 1; i <= 5; i++)
        {
            cin >> a[i];
            a[i]++;
        }
        pr = max (pr, lca (a[1], a[2]));
        ans += pr.se;
        for (int i = 2; i <= 5; i++){
            pr = {0, 100000};
            for (int j = 1; j < i; j++)
            {
                pr = max (pr, lca (a[i], a[j]));
            }
            ans += pr.se;
        }
        cout << ans << "\n";
    }
}

int main ()
{
    iosBASE;
    int t = 1;
    while (t--)
    {
        ma1n ();
    }
    return 0;
}

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