Submission #765377

#	Time	Username	Problem	Language	Result	Execution time	Memory
765377		Pragmatism	Roadside Advertisements (NOI17_roadsideadverts)	C++17	100 / 100	50 ms	15492 KiB

roadsideadverts

//Bismillahir-Rahmanir-Rahim

#include <bits/stdc++.h>
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#define pb push_back
#define pii pair <int, int>
#define pll pair <long long, long long>
#define pld pair <ld, ld>
#define ll long long
#define ld long double
#define x first
#define y second
#define all(v) v.begin(),v.end()
#define sz(s) (int)s.size()
#define skip continue
#define bpop(x) (ll)__builtin_popcountll(x)

using namespace std;

const int N = 5e4 + 7;
const int M = 3e5 + 7;
const int MAXA = 1e6 + 7;
const int inf = 1e9 + 7;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ld eps = 1e-4;

pii dir[] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

#define int long long

int n, q, T, sum[N], tin[N], tout[N], dist[N], p[N][17];
vector <pii> g[N];
void dfs(int v, int pr) {
    p[v][0] = pr, tin[v] = ++T;
    for (int k = 1;k < 17;k++)p[v][k] = p[p[v][k - 1]][k - 1];
    for (auto to : g[v]) {
        if (to.x == pr)skip;
        dist[to.x] = dist[v] + 1, sum[to.x] = sum[v] + to.y, dfs(to.x, v);
    }
    tout[v] = ++T;
}
bool upper(int a, int b) {
    return (tin[a] <= tin[b] && tout[a] >= tout[b]);
}
int get_lca(int a, int b) {
    if (dist[a] > dist[b])swap(a, b);
    if (upper(a, b))return a;
    for (int k = 16;k >= 0;k--) {
        if (!upper(p[a][k], b))a = p[a][k];
    }
    return p[a][0];
}
void solve() {
    cin >> n;
    tin[0] = -inf, tout[0] = inf;
    for (int i = 1;i < n;i++) {
        int a, b, w;
        cin >> a >> b >> w;
        a++, b++;
        g[a].pb({b, w}), g[b].pb({a, w});
    }
    dfs(1, 0);
    cin >> q;
    for (int i = 1;i <= q;i++) {
        vector <int> v(6);
        for (int i = 1;i <= 5;i++)cin >> v[i], v[i]++;
        int LCA = v[1];
        for (int i = 2;i <= 5;i++)LCA = get_lca(LCA, v[i]);
        int ans = sum[v[1]] - sum[LCA];
        for (int i = 2;i <= 5;i++) {
            int mxlca = 0, mx = -inf;
            for (int j = 1;j < i;j++) {
                int lca = get_lca(v[j], v[i]);
                if (dist[lca] > mx)mx = dist[lca], mxlca = lca;
            }
            ans += sum[v[i]] - sum[mxlca];
        }
        cout << ans << '\n';
    }
}
signed main() {
    //srand(time(NULL));
    //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("cows.in", "r", stdin);
    //freopen("cows.out", "w", stdout);
    int test;
    test = 1;
    //cin >> test;
    for (int i = 1;i <= test;i++) {
        //cout << "Case " << i << ": ";
        solve();
    }
    return 0;
}

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