제출 #849012

#제출 시각아이디문제언어결과실행 시간메모리
849012BidoTeima경주 (Race) (IOI11_race)C++17
0 / 100
3 ms14424 KiB
//#pragma once #include "race.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2e5 + 3; int k; vector<pair<int,int>>adj[N]; bool marked[N]; int sub[N]; int sz; int ans = 1e9; int dfs_subtree(int node, int prev){ sub[node] = 1; for(auto& edge : adj[node]){ if(edge.first != prev && !marked[edge.first]){ sub[node] += dfs_subtree(edge.first, node); } } return sub[node]; } int find_centroid(int node, int prev){ for(auto& edge : adj[node]){ if(edge.first != prev && !marked[edge.first] && 2 * sub[edge.first] > sz){ return find_centroid(edge.first, node); } } return node; } vector<pair<int,int>>weights[N]; vector<pair<int,int>>all; void dfs(int start, int node, int prev, int cur, int len){ if(cur>k)return; weights[start].push_back({cur,len}); all.push_back({cur,len}); for(auto & edge : adj[node]){ if(edge.first != prev && !marked[edge.first]){ dfs(start, edge.first, node, cur + edge.second, len + 1); } } } void decompose(int node){ dfs_subtree(node, -1); sz = sub[node]; int c = find_centroid(node, -1); all.push_back(make_pair(0,0)); for(auto& edge : adj[c]){ if(marked[edge.first])continue; dfs(edge.first, edge.first, c, edge.second, 1); } for(auto& edge : adj[c]){ if(marked[edge.first])continue; int child = edge.first; for(auto& p : weights[child]){ int d = k - p.first; // child either doesnt have d or has (d, l), (d, l + 1), ..., (d, r) auto l = lower_bound(weights[child].begin(), weights[child].end(), make_pair(d,0)); if(l == weights[child].end() || l->first != d){//child doesnt have d auto it = lower_bound(all.begin(),all.end(),make_pair(d,0)); if(it != all.end() && it->first == d){ ans = min(ans, p.second + it->second); } }else{ auto r = upper_bound(weights[child].begin(), weights[child].end(), make_pair(d, (int)1e9)) - 1; auto it = lower_bound(all.begin(), all.end(), make_pair(d,0)); if(it->second >= l->second){ it = upper_bound(all.begin(),all.end(),make_pair(r->first, r->second)); if(it != all.end() && it->first == d){ ans = min(ans, p.second + it->second); } }else{ ans = min(ans, p.second + it->second); } } } } marked[c] = 1; all.clear(); all.shrink_to_fit(); for(auto& edge : adj[c]){ int child = edge.first; if(!marked[child]){ weights[child].clear(); weights[child].shrink_to_fit(); //decompose(child); } } for(auto&edge:adj[c]){ if(!marked[edge.first])decompose(edge.first); } } int best_path(int N, int K, int H[][2], int L[]) { k=K; for(int i = 0; i < N - 1; i++){ adj[H[i][0]].push_back({H[i][1],L[i]}); adj[H[i][1]].push_back({H[i][0],L[i]}); } decompose(0); return 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...