Submission #495715

#TimeUsernameProblemLanguageResultExecution timeMemory
495715PietraRace (IOI11_race)C++14
21 / 100
3054 ms14576 KiB
#include<bits/stdc++.h> using namespace std ; #include "race.h" const int inf = 1e9 + 5 ; const int maxn = 2e5 + 5 ; const int MAXN = 1e6 + 5 ; int sz[maxn], mark[maxn], ans, n, k, f[MAXN] ; vector<pair<int,int>> grafo[maxn] ; void dfs(int v, int p){ sz[v] = 1 ; for(auto a : grafo[v]){ if(a.first == p || mark[a.first]) continue ; dfs(a.first, v) ; sz[v] += sz[a.first] ; } } int find_cent(int v, int p, int szz){ for(auto a : grafo[v]){ if(a.first == p || mark[a.first] || 2*sz[a.first] <= szz) continue ; find_cent(a.first, v, szz) ; } return v ; } void make_count(int type, int v, int p, int dist, int lvl){ if(dist > k) return ; if(type == -1) f[dist] = inf ; else f[dist] = min(f[dist], lvl) ; for(auto a : grafo[v]){ if(a.first == p || mark[a.first]) continue ; make_count(type, a.first, v, dist+a.second, lvl+1) ; } } void add(int v, int p, int dist, int lvl){ if(dist > k) return ; ans = min(ans, f[k-dist] + lvl) ; for(auto a : grafo[v]){ if(a.first == p || mark[a.first]) continue ; add(a.first, v, dist + a.second, lvl+1) ; } } void make_graph(int v, int p){ dfs(v, p) ; int c = find_cent(v, p, sz[v]) ; mark[c] = 1 ; f[0] = 0 ; for(auto a : grafo[c]){ if(a.first == p || mark[a.first]) continue ; add(a.first, c, a.second, 1) ; make_count(0, a.first, c, a.second, 1) ; } for(auto a : grafo[c]){ if(a.first == p || mark[a.first]) continue ; make_count(-1, a.first, c, a.second, 1) ; } for(auto a : grafo[c]){ if(a.first == p || mark[a.first]) continue ; make_graph(a.first, c) ; } } int best_path(int N, int K, int H[maxn][2], int L[maxn]) { for(int i = 0 ; i < N - 1 ; i++){ grafo[H[i][0]].push_back({H[i][1], L[i]}) ; grafo[H[i][1]].push_back({H[i][0], L[i]}) ; } k = K ; for(int i = 1 ; i <= K ; i++) f[i] = inf ; ans = inf ; make_graph(0, -1) ; return (ans == inf ? -1 : ans) ; } // int32_t main(){ // ans = inf ; // cin >> n >> k ; // for(int i = 0 ; i < n-1 ; i++){ // int a, b, c ; // cin >> a >> b >> c ; // grafo[a].push_back({b, c}), grafo[b].push_back({a, c}) ; // } // for(int i = 1 ; i <= k ; i++) f[i] = inf ; // make_graph(0, -1) ; // cout << ans << "\n" ; // }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...