제출 #765098

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
765098		vjudge1	Roadside Advertisements (NOI17_roadsideadverts)	C++17	100 / 100	100 ms	23860 KiB

roadsideadverts

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define ent '\n'
#define all(x) x.begin(), x.end()
#define s second
#define f first
#define pb push_back
typedef long long ll;
using namespace std;
const int maxn = 2e5 + 250;
const int mod = 1e9 + 7;
const int K = 400;
const double Pi = acos(-1.0);
const long double eps = 1e-9;
#define int long long
int a[maxn], pref[maxn];
vector<pair<int,int>>g[maxn];
int tin[maxn], tout[maxn], lev[maxn];
int p[30][maxn];
int timer;
void dfs(int v, int pa = 1) {
    lev[v] = lev[pa]+1;
    tin[v] = timer++;
    p[0][v] = pa;
    for(int i = 1;i < 30; i++) {
        p[i][v] = p[i-1][p[i-1][v]];
    }
    for(auto to:g[v]) {
        if(to.f==pa)continue;
            pref[to.f] = pref[v]+to.s;
            dfs(to.f, v);
    }
    tout[v] = timer-1;
}

bool parent(long long u, long long v) {
    if(tin[u] <= tin[v] && tout[u] >= tout[v]) {
        return 1;
    }
    return 0;
}

int lca(long long u, long long v) {
    if(lev[u] < lev[v]) {
        swap(u, v);
    }
    for(long long i = 25; i >= 0; i--) {
        if(lev[u] - (1<<i) >= lev[v]) {
            u = p[i][u];
        }
    }
    if(u == v) return u;
    for(long long i = 25; i >= 0; i--) {
        if(p[i][u] != p[i][v]) {
            u = p[i][u];
            v = p[i][v];
        }
    }
    return p[0][v];
}
void solve() {
    int n, k;
    cin >> n;
    for(int i = 1;i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u++,v++;
        g[u].pb({v, w});
        g[v].pb({u, w});
    }
    dfs(1);
    cin >> k;
    for(int i = 1;i <= k; i++) {
        int sum = 0;
        for(int j = 1;j <= 5; j++) {
            cin >> a[j];
            a[j]++;
        }
        int x = a[1];
        for(int j = 2;j <= 5; j++) {
            x = lca(x, a[j]);
        }
        for(int j = 1;j <= 5; j++) {
            sum += pref[a[j]]-pref[x];
        }
        for(int j = 1;j <= 5; j++) {
            int mx = 0;
            for(int l = j+1;l <= 5; l++) {
                mx = max(mx, pref[lca(a[j], a[l])]-pref[x]);
            }
            sum -= mx;
        }
        cout << sum << ent;
    }
}
signed main () {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // freopen("position.in", "r" , stdin);
    // freopen("position.out", "w", stdout);
    int t = 1;
    // cin >> t;
    for(int i = 1;i <= t; i++) {
        // cout << "Case #" << i << ": ";
        solve();    
    }
}

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