제출 #587563

#제출 시각아이디문제언어결과실행 시간메모리
587563Bobonbush경주 (Race) (IOI11_race)C++17
0 / 100
1 ms340 KiB
#include <bits/stdc++.h> #define foreach for #define in : using namespace std; typedef long long ll; /* Konichiwa Konichiwa Ara ~~ ara Bob no taisuki - Shinobu Kocho * * * * * * * * * * * I love SHINOBU <3 <3 <3 * * * * * * * * * */ /* _________________________ Author : Bob15324 _________________________ */ template<class X , class Y> bool Minimize(X & x , Y y) { if((x == 0 || x == -1) || (x >y && y > 0)) { x = y; return true; } return false; } template<class X , class Y> bool Maximize(X & x , Y y) { if( x < y) { x = y; return true; } return false; } /* End of templates. Let's see what do we have here */ const int N = 2e5+1; int res = -1; class GRAPH { private: vector<set<pair<int ,int >>>vertices; vector<int>sub_size; vector<map<int ,int >>dict; public: GRAPH(int _n) { vertices.resize(_n+1); sub_size.resize(_n+1); dict.resize(_n+1); } void AddEdge(int u ,int v ,int w) { vertices[u].insert(make_pair(v , w)); vertices[v].insert(make_pair(u , w)); } int DFS(int u ,int daddy) { sub_size[u] = 1; foreach(pair<int ,int > adj in vertices[u]) { int v = adj.first; if(v == daddy) { continue; } sub_size[u] += DFS(v , u); } return sub_size[u]; } int centroid(int u ,int daddy , int lim) { foreach(pair<int ,int > adj in vertices[u]) { int v = adj.first; if(v == daddy) { continue; } if(sub_size[v] > lim) { return centroid(v , u , lim); } } return u; } void dfs2(int u ,int daddy ,int base , int distance , int s ,int k) { foreach(pair<int , int >adj in vertices[u]) { int v = adj.first; if ( v== daddy) { continue; } if(s + adj.second > k) { continue; } dfs2(v , u , base , distance + 1 , s + adj.second , k); } Minimize(dict[base][s] , distance ); if(dict[base][k-s] != 0) { Minimize(res , dict[base][k - s] + distance); } } void Build(int u, int daddy ,int k ) { int lim = DFS(u , daddy); int _c = centroid(u , daddy , lim >> 1); dfs2(_c , daddy , _c , 0 , 0 , k); set<pair<int ,int >> temp = vertices[_c]; foreach(pair<int ,int > adj in temp ) { vertices[_c].erase(adj); vertices[adj.first].erase(make_pair(_c , adj.second)); Build(adj.first , _c , k); } } }; int best_path(int n , int m ,int H[][2] , int L[]) { GRAPH graph(n); for(int i = 0 ; i < n -1 ; i++) { H[i][0]++; H[i][1]++; graph.AddEdge(H[i][0] , H[i][1] , L[i]); } graph.Build(1 , - 1 , m); return res; } //Ehem. My code is amazing. Pay me 2$.Thank you.
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...