제출 #471060

#제출 시각아이디문제언어결과실행 시간메모리
471060jli12345경주 (Race) (IOI11_race)C++14
0 / 100
3 ms4940 KiB
#include <bits/stdc++.h> using namespace std; void fastIO(){ ios_base::sync_with_stdio(false); cin.tie(0); } typedef long long ll; vector<pair<int, int> > edges[200100]; int sub[200100]; bool rem[200100]; int LEN; void dfs(int node, int pa = 0){ sub[node] = 1; for (pair<int, int> nx : edges[node]){ if (nx.first == pa || rem[nx.first]) continue; dfs(nx.first, node); sub[node] += sub[nx.first]; } } int centroid(int node, int sz, int pa = 0){ for (pair<int, int> nx : edges[node]){ if (nx.first == pa || rem[nx.first]) continue; if (sub[nx.first] > sz/2) return centroid(nx.first, sz, node); } return node; } void dfs2(int node, ll dep, int cur, map<ll, int> &mp, int pa = 0){ if (mp.count(dep)) mp[dep] = min(mp[dep], cur); else mp[dep] = cur; for (pair<int, int> nx : edges[node]){ if (nx.first == pa || rem[nx.first]) continue; dfs2(nx.first, dep+nx.second, cur+1, mp, node); } } int INF = 0x3f3f3f3f; int decomp(int node){ dfs(node); int cent = centroid(node, sub[node]); rem[cent] = true; map<ll, int> mp; int curmin = INF; mp[0] = 0; for (pair<int, int> nx : edges[cent]){ if (rem[nx.first]) continue; map<ll, int> tmp; dfs2(nx.first, nx.second, 1, tmp); for (auto it = tmp.begin(); it != tmp.end(); it++){ if (mp.count(LEN-(*it).first)) curmin = min(curmin, (*it).second+mp[LEN-(*it).first]); } for (auto it = tmp.begin(); it != tmp.end(); it++){ if (!mp.count((*it).first)) mp[(*it).first] = (*it).second; else mp[(*it).first] = min(mp[(*it).first], (*it).second); } } int totmin = curmin; for (pair<int, int> nx : edges[cent]){ if (rem[nx.first]) continue; totmin = min(totmin, decomp(nx.first)); } return totmin; } int best_path(int N, int K, int H[][2], int *L){ LEN = K; for (int i = 0; i < N-1; i++){ int a = H[i][0], b = H[i][1]; a++, b++; edges[a].push_back({b, L[i]}); edges[b].push_back({a, L[i]}); } return decomp(1); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...