Submission #278771

#TimeUsernameProblemLanguageResultExecution timeMemory
278771Haunted_CppRoadside Advertisements (NOI17_roadsideadverts)C++17
7 / 100
198 ms13688 KiB
/** * author: Haunted_Cpp **/ #include <bits/stdc++.h> using namespace std; #pragma GCC optimize("Ofast") #pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native") #pragma GCC optimize("unroll-loops") template<typename T> ostream &operator << (ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; } template<typename T, size_t size> ostream &operator << (ostream &os, const array<T, size> &arr) { os << '{'; string sep; for (const auto &x : arr) os << sep << x, sep = ", "; return os << '}'; } template<typename A, typename B> ostream &operator << (ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; } void debug_out() { cerr << endl; } template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << ' ' << H; debug_out(T...); } #ifdef LOCAL #define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__) #else #define debug(...) 47 #endif const int MAX_N = 5e4 + 5; const int MAX_K = 20 + 5; int Time = 0; vector<int> depth(MAX_N), dist(MAX_N), in(MAX_N), out(MAX_N); vector<vector<int>> dp(MAX_N, vector<int>(MAX_K, -1)); vector<vector<pair<int, int>>> g(MAX_N); void dfs(int node = 0, int p = -1) { in[node] = ++Time; dp[node][0] = p; for (auto to : g[node]) { if (to.first != p) { depth[to.first] = depth[node] + 1; dist[to.first] = dist[node] + to.second; dfs(to.first, node); } } out[node] = Time; } int kth(int node, int diff) { assert(diff >= 0); for (int i = MAX_K - 1; ~i; i--) { if ((diff >> i) & 1) { node = dp[node][i]; } } return node; } int lca(int u, int v) { if (depth[u] < depth[v]) swap(u, v); u = kth(u, depth[u] - depth[v]); if (u == v) return u; for (int i = MAX_K - 1; ~i; i--) { if (dp[u][i] != dp[v][i]) { u = dp[u][i]; v = dp[v][i]; } } return dp[u][0]; } int get_dist(int u, int v) { return dist[u] + dist[v] - 2 * dist[lca(u, v)]; } bool in_subtree(int u, int v) { return (in[u] <= in[v] && out[u] >= out[v]); } int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for (int i = 0; i < n - 1; i++) { int st, et, w; cin >> st >> et >> w; g[st].emplace_back(et, w); g[et].emplace_back(st, w); } dfs(); for (int j = 1; j < MAX_K; j++) { for (int i = 0; i < n; i++) { if (~dp[i][j - 1]) { dp[i][j] = dp[dp[i][j - 1]][j - 1]; } } } int q; cin >> q; const int T = 5; vector<pair<int, int>> arr(T); while(q--) { for (int i = 0; i < T; i++) { cin >> arr[i].second; arr[i].first = depth[arr[i].second]; } pair<int, int> best_way = {1e9, 1e9}; for (int i = 0; i < T; i++) { for(int j = 0; j < T; j++) { const int LCA = lca(arr[i].second, arr[j].second); best_way = min(best_way, {depth[LCA], LCA}); } } sort(arr.begin(), arr.end()); set<int> vis; function<int(int)> solve = [&](int source) { vis.insert(source); const int d = depth[source]; int s = 0; for (int i = 0; i < T; i++) { const int TO = arr[i].second; if(vis.find(TO) != vis.end()) continue; if (d < depth[TO] && in_subtree(source, TO)) { vis.insert(TO); s += get_dist(source, TO) + solve(TO); } } return s; }; cout << solve(best_way.first) << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...