Submission #321718

#TimeUsernameProblemLanguageResultExecution timeMemory
321718arujbansalRoadside Advertisements (NOI17_roadsideadverts)C++17
100 / 100
125 ms16236 KiB
#include <bits/stdc++.h> #define FAST_IO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr) #define setIO(i, o) freopen(i, "r", stdin), freopen(o, "w", stdout) #define seed() srand(chrono::steady_clock::now().time_since_epoch().count()) #define pb push_back #define eb emplace_back #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define sz(x) (int) (x).size() #define lc(i) 2*i #define rc(i) 2*i+1 //#define int long long using namespace std; using ll = long long; using ii = pair<int, int>; using vii = vector<ii>; using vi = vector<int>; using vvi = vector<vi>; using vb = vector<bool>; using vvb = vector<vb>; ll rng() { ll a = rand(); ll b = rand(); return a * (RAND_MAX + 1ll) + b; } const int N = 5e4 + 5, MOD = 1e9 + 7, INF = 1e9 + 5; vii g[N]; //int nodeWt[N]; struct LCA { int n, k, timer; vector<int> tin, tout; vector<vector<pair<int, int>>> par; void init(int x) { n = x; k = 31 - __builtin_clz(n); timer = 0; tin.resize(n); tout.resize(n); par.assign(n, vector<pair<int, int>>(k + 1, {0, 0})); } void dfs(int u = 0, int p = -1, int lastWt = 0) { tin[u] = timer++; // nodeWt[u] = lastWt; par[u][0].first = (p == -1 ? 0 : p); par[u][0].second = lastWt; for (int j = 1; j <= k; j++) { par[u][j].first = par[par[u][j - 1].first][j - 1].first; par[u][j].second = par[u][j - 1].second + par[par[u][j - 1].first][j - 1].second; } for (const auto &[v, wt] : g[u]) if (v != p) dfs(v, u, wt); tout[u] = timer - 1; } bool isAnc(int x, int v) { return tin[x] <= tin[v] && tout[x] >= tout[v]; } int getLCA(int u, int v) { if (isAnc(u, v)) return u; if (isAnc(v, u)) return v; for (int j = k; j >= 0; j--) if (!isAnc(par[u][j].first, v)) u = par[u][j].first; return par[u][0].first; } int getCost(int u, int v) { if (u == v) return 0; int ans = 0; for (int j = k; j >= 0; j--) { if (isAnc(par[u][j].first, v)) continue; ans += par[u][j].second; u = par[u][j].first; } return ans + par[u][0].second; } }; void solve() { int n; cin >> n; for (int i = 1; i < n; i++) { int u, v, w; cin >> u >> v >> w; g[u].eb(v, w); g[v].eb(u, w); } LCA binlift; binlift.init(n); binlift.dfs(); int q; cin >> q; while (q--) { vi qry(5); for (auto &x : qry) cin >> x; sort(all(qry), [&](const auto &x, const auto &y) { return binlift.tin[x] < binlift.tin[y]; }); // for (const auto &x : qry) cout << x << " "; // cout << "\n"; int root = binlift.getLCA(qry[0], qry[1]); for (int i = 2; i < 5; i++) root = binlift.getLCA(root, qry[i]); int ans = binlift.getCost(qry[0], root); for (int i = 1; i < 5; i++) { int lca = binlift.getLCA(qry[i - 1], qry[i]); // cout << "LCA: " << lca << " v: " << qry[i] << "\n"; ans += binlift.getCost(qry[i], lca); // cout << ans << "\n"; } // cout << binlift.par[2][0].second; cout << ans << "\n"; } } signed main() { FAST_IO; #ifdef arujbansal_local setIO("input.txt", "output.txt"); #endif seed(); int tc = 1; // cin >> tc; while (tc--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...