Submission #1164949

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164949		DangKhoizzzz	Roadside Advertisements (NOI17_roadsideadverts)	C++20	7 / 100	100 ms	17852 KiB

roadsideadverts

// giao phai CBVD chill buoi toi

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii pair <int , int>
#define arr3 array <int , 3>

/*
+ array limit ???
+ special case ??? n = 1?
+ time limit ???
*/

using namespace std;

const int INF = 1e18 + 7;
const int maxn = 2e5 + 7;

int n , q , jump[maxn][20] , depth[maxn] , dp[maxn];
vector <pii> g[maxn];

void dfs_build(int u , int p)
{
    for(pii e: g[u])
    {
        int v = e.fi , w = e.se;
        if(v == p) continue;
        depth[v] = depth[u] + 1;
        jump[v][0] = u;
        dp[v] = dp[u] + w;
        dfs_build(v , u);
    }
}

int LCA(int u , int v)
{
    if(depth[u] > depth[v]) swap(u , v);
    for(int i = 19; i >= 0; i--)
    {
        if(depth[jump[v][i]] >= depth[u])
        {
            v = jump[v][i];
        }
    }
    if(u == v) return u;
    for(int i = 19; i >= 0; i--)
    {
        if(jump[u][i] != jump[v][i])
        {
            u = jump[u][i];
            v = jump[v][i];
        }
    }
    return jump[u][0];
}

void build()
{
    dfs_build(1 , 1);
    for(int j = 1; j <= 20; j++)
    {
        for(int i = 1; i <= n; i++)
        {
            jump[j][i] = jump[j-1][jump[j-1][i]];
        }
    }
}

void solve_case()
{
    array <int , 5> node;
    for(int i = 0; i < 5; i++) cin >> node[i];
    for(int i = 0; i < 5; i++) node[i]++;

    int ans = 0;

    for(int mask = 1; mask < (1 << 5); mask++)
    {
        int lca = -1;
        int cnt = -1;

        for(int i = 0; i < 5; i++)
        {
            if((mask >> i)&1)
            {
                if(lca == -1) lca = node[i];
                else lca = LCA(lca , node[i]);
                cnt *= -1;
            }
        }
        ans += cnt*(dp[lca]);
    }

    cout << ans << '\n';
}

void solve()
{
    cin >> n;
    for(int i = 1; i < n; i++)
    {
        int u , v , w;
        cin >> u >> v >> w;
        u++ , v++;
        g[u].push_back({v , w});
        g[v].push_back({u , w});
    }
    build();
    cin >> q;
    while(q--)
    {
        solve_case();
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

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