Submission #334451

#	Time	Username	Problem	Language	Result	Execution time	Memory
334451		ncduy0303	Roadside Advertisements (NOI17_roadsideadverts)	C++17	100 / 100	91 ms	12268 KiB

roadsideadverts

#include <bits/stdc++.h>

using namespace std;

#define ar array
#define ll long long

const int MAX_N = 5e4 + 1;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll LINF = 1e18;

const int MAX_L = 18;

int n, q, par[MAX_N][MAX_L], dep[MAX_N], dist[MAX_N];
int timer, tin[MAX_N];
vector<ar<int,2>> adj[MAX_N];
 
void dfs(int u, int p = 0) {
    par[u][0] = p;
    tin[u] = ++timer;
    for (int i = 1; i < MAX_L; i++) 
        par[u][i] = par[par[u][i - 1]][i - 1];
    for (auto [v, w] : adj[u]) {
        if (v == p) continue;
        dep[v] = dep[u] + 1;
        dist[v] = dist[u] + w;
        dfs(v, u);
    }
}
 
int ancestor(int u, int k) {
    for (int i = 0; i < MAX_L; i++) 
        if (k & (1 << i)) 
            u = par[u][i];
    return u;
}
 
int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    u = ancestor(u, dep[u] - dep[v]);
    if (u == v) return u;
    for (int i = MAX_L - 1; i >= 0; i--)
        if (par[u][i] != par[v][i])
            u = par[u][i], v = par[v][i];
    return par[u][0];
}

int query(int u, int v) {
    return dist[u] + dist[v] - 2 * dist[lca(u, v)];
}

bool cmp(int u, int v) {
    return tin[u] < tin[v];
}

void solve() {
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v, w; cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    dfs(0);
    cin >> q;
    while (q--) {
        vector<int> a(5);
        for (int i = 0; i < 5; i++) cin >> a[i];
        sort(a.begin(), a.end(), cmp);
        
        int ans = query(a[0], lca(a[0], a[4]));
        for (int i = 1; i < 5; i++) {
            ans += query(a[i], lca(a[i], a[i - 1]));
        }
        cout << ans << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    int tc = 1;
    // cin >> tc;
    for (int t = 1; t <= tc; t++) {
        // cout << "Case #" << t  << ": ";
        solve();
    }
}

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