제출 #789096

#제출 시각아이디문제언어결과실행 시간메모리
789096diobrando97경주 (Race) (IOI11_race)C++17
0 / 100
7 ms12116 KiB
#include <bits/stdc++.h> #pragma GCC optimize(3) #define ll long long #define pii pair<int, int> #define pll pair<long long, long long> #define F first #define S second #define endl '\n' using namespace std; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; const int N = 2e5 + 5; double startTime = clock(); double getCurrentTime() { return (double)(clock() - startTime) / CLOCKS_PER_SEC; } int n, k; int ans = inf; int tot = 0, cur = 0; array<int, 3> dis[N]; multiset<int> st[N]; struct CD{ int n; vector<vector<pii>> g; vector<int> par, sz; vector<bool> vis; CD(){} CD(int n){ init(n); } void init(int n){ this->n = n; g.assign(n+1, {}); par.assign(n+1, 0); sz.assign(n+1, 0); vis.assign(n+1, 0); } void addEdge(int x, int y, int w){ g[x].push_back({y, w}); g[y].push_back({x, w}); } void dfs(int i, int f){ sz[i] = 1; for(auto [j, w] : g[i]){ if(j == f || vis[j]) continue; dfs(j, i); sz[i] += sz[j]; } } int getCentroid(int i, int f, int n){ for(auto [j, w] : g[i]){ if(j == f || vis[j]) continue; if(sz[j] * 2 > n) return getCentroid(j, i, n); } return i; } void dfs2(int i, int f, int w, int len, int mark){ if(w > k) return; dis[++tot] = {w, len, mark}; for(auto [j, wj] : g[i]){ if(j == f || vis[j]) continue; dfs2(j, i, w+wj, len+1, mark); } } void work(int i, int f = 0){ dfs(i, f); int cen = getCentroid(i, f, sz[i]); vis[cen] = 1; par[cen] = f; tot = cur = 0; for(auto [j, w] : g[cen]){ if(j == f || vis[j]) continue; dfs2(j, i, w, 1, ++cur); } st[0] = {0}; for(int j=1; j<=tot; j++){ st[dis[j][0]].insert(dis[j][1]); } int x = 1, y = 1; for(int j=1; j<=cur; j++){ while(x <= tot && dis[x][2] == j){ st[dis[x][0]].erase(st[dis[x][0]].find(dis[x][1])); x++; } while(y <= tot && dis[y][2] == j){ int tar = k - dis[y][0]; if(tar >= 0 && tar <= k && !st[tar].empty()){ ans = min(ans, dis[y][1] + *st[tar].begin()); } y++; } } for(auto [j, w] : g[cen]){ if(vis[j]) continue; work(j, cen); } } }; int best_path(int N, int K, int h[][2], int l[]) { n = N; k = K; CD cent(n); for (int i = 0; i < n - 1; i++) { int x = h[i][0] + 1, y = h[i][1] + 1, w = l[i]; cent.addEdge(x, y, w); } memset(dis, 0, sizeof dis); for(int i=1; i<=n; i++) st[i].clear(); cent.work(1, 0); return (ans == inf ? -1 : ans); // cout << (ans == inf ? -1 : ans) << endl; } // void solve(){ // cin >> n >> k; // CD cent(n); // for(int i=1; i<n; i++){ // int x, y, w; cin >> x >> y >> w; // x++; y++; // cent.addEdge(x, y, w); // } // memset(dis, 0, sizeof dis); // for(int i=1; i<=n; i++) st[i].clear(); // cent.work(1, 0); // cout << (ans == inf ? -1 : ans) << endl; // } // int main(){ // ios::sync_with_stdio(0); cin.tie(0); // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); // int t = 1; // //cin >> t; // while(t--) // solve(); // return 0; // }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...