Submission #1114992

#TimeUsernameProblemLanguageResultExecution timeMemory
1114992gustavo_dRace (IOI11_race)C++17
0 / 100
64 ms71240 KiB
#include "race.h" #include <bits/stdc++.h> using namespace std; #pragma GCC optimize("O3,unroll-loops") const int MAXN = 2e5; const int MAXV = 1e6+1; vector<pair<int, int>> adj[MAXN]; bool vis[MAXN]; int sz[MAXN]; bool in[MAXN]; int n, k; void dfs(int v) { vis[v] = true; sz[v] = 1; for (auto& [viz, w] : adj[v]) { if (vis[viz]) continue; dfs(viz); sz[v] += sz[viz]; } } int find_centroid(int v, int pai) { // cout << "buscando centroid " << v << endl; pair<int, int> mx = {v, 0}; for (auto& [viz, w] : adj[v]) { if (viz == pai or in[viz]) continue; if (mx.second < sz[viz]) mx = {viz, sz[viz]}; } if (mx.second <= n / 2) { // cout << "é" << v <<endl; return v; } return find_centroid(mx.first, v); } vector<int> sub_mn_depth(MAXV, 1e8); vector<pair<int, int>> dists[MAXV]; vector<int> sub_dists; void get_dist(int v, int pai, int dist, int depth) { sub_mn_depth[dist] = min(sub_mn_depth[dist], depth); sub_dists.push_back(dist); for (auto& [viz, w] : adj[v]) { if (viz == pai or in[viz]) continue; get_dist(viz, v, dist + w, depth+1); } } int ans = 1e8; void decomp(int v) { int centroid = find_centroid(v, -1); in[centroid] = true; vector<int> all_dists; // if (centroid == 8) cout << centroid << " é centroid decompondo" << v << endl; for (auto& [viz, w] : adj[centroid]) { if (in[viz]) continue; get_dist(viz, centroid, w, 1); for (int d : sub_dists) { dists[d].push_back({sub_mn_depth[d], viz}); sub_mn_depth[d] = 1e8; all_dists.push_back(d); } sub_dists.clear(); } for (int d : all_dists) { sort(dists[d].begin(), dists[d].end()); } if (!dists[k].empty()) ans = min(ans, dists[k][0].first); for (auto& [viz, w] : adj[centroid]) { if (in[viz]) continue; get_dist(viz, centroid, w, 1); for (int d : sub_dists) { for (int i=0; d <= k and i<min(2, (int)dists[k-d].size()); i++) { if (dists[k-d][i].second == viz) continue; ans = min(ans, dists[k-d][i].first + sub_mn_depth[d]); } sub_mn_depth[d] = 1e8; } sub_dists.clear(); } for (int d : all_dists) dists[d].clear(); for (auto& [viz, w] : adj[centroid]) { if (in[viz]) continue; decomp(viz); } in[centroid] = false; } int best_path(int N, int K, int H[][2], int L[]) { n = N; k = K; for (int i=0; i<N-1; i++) { int u = H[i][0], v = H[i][1]; int w = L[i]; adj[u].push_back({v, w}); adj[v].push_back({u, w}); } dfs(0); decomp(0); return (ans == (int)1e8 ? -1 : ans); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...