Submission #1209216

#TimeUsernameProblemLanguageResultExecution timeMemory
1209216vache_kocharyan경주 (Race) (IOI11_race)C++20
0 / 100
1 ms320 KiB
//#include "race.h" #include <bits/stdc++.h> #include <unordered_set> #include <unordered_map> using namespace std; vector<vector<pair<int, int>>>G; int answ = 1e9, compSize, maxDep, maxMaxDep; const int NN = 2e5 + 5; unordered_map<int, set<int>>depth, cur_depth; bool used[NN]; int sz[NN]; int k; void merge_(set<int>&a, set<int>b) { for (auto i : b) a.insert(i); } void dfs(int node, int parent) { sz[node] = 1; for (auto i : G[node]) { if (i.first == parent || used[i.first]) continue; dfs(i.first, node); sz[node] += sz[i.first]; } } int find_centroid(int node, int parent) { for (auto i : G[node]) { if (i.first == parent || used[i.first]) continue; if (sz[i.first] * 2 >= compSize) return find_centroid(i.first, node); } return node; } int centroid(int u) { dfs(u, -1); compSize = sz[u]; return find_centroid(u, -1); } void solve(int node, int parent, int node_depth, int node_sum) { if (node_sum > k) return; if (node_sum == k) { answ++; return; } cur_depth[node_sum].insert(node_depth); if (!depth[k - node_sum].empty()) { answ = min(answ, node_depth + *depth[k - node_sum].begin()); } for (auto i : G[node]) { if (i.first == parent || used[i.first]) continue; solve(i.first, node, node_depth + 1, node_sum + i.second); if (parent != -1) continue; for (auto it : cur_depth) { merge_(depth[it.first], it.second); it.second.clear(); } } } void centroid_decomposition() { queue<int>q; q.push(0); while (!q.empty()) { int u = q.front(); q.pop(); int c = centroid(u); solve(c, -1, 0, 0); depth.clear(); used[c] = true; for (auto i : G[c]) { if (used[i.first]) continue; q.push(i.first); } } } int best_path(int N, int K, int H[][2], int L[]) { k = K; G.resize(N + 1); for (int i = 0; i < N - 1; i++) { G[H[i][0]].push_back({ H[i][1], L[i] }); G[H[i][1]].push_back({ H[i][0], L[i] }); } centroid_decomposition(); if (answ == 1e9) return -1; return answ; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...