제출 #854811

#제출 시각아이디문제언어결과실행 시간메모리
854811hngwlog경주 (Race) (IOI11_race)C++14
9 / 100
65 ms25136 KiB
#include <bits/stdc++.h> #include "race.h" using namespace std; #define fi first #define se second #define _size(x) (int)x.size() #define BIT(i, x) ((x >> i) & 1) #define MASK(n) ((1 << n) - 1) #define REP(i, n) for (int i = 0, _n = (n); i < _n; i++) #define FOR(i, a, b) for (int i = a, _b = (b); i <= _b; i++) #define FORD(i, a, b) for (int i = a, _b = (b); i >= _b; i--) #define FORB1(i, mask) for (int i = mask; i > 0; i ^= i & - i) #define FORB0(i, n, mask) for (int i = ((1 << n) - 1) ^ mask; i > 0; i ^= i & - i) #define FORALL(i, a) for (auto i: a) #define fastio ios_base::sync_with_stdio(0); cin.tie(0); const int inf = 1e9; struct edgeNode { int u, v; long long w; }; int ans = inf; vector<int> used, depth, inSt; vector<long long> dist; vector<edgeNode> edge; vector<vector<int>> adj; vector<set<pair<long long, int>>> st; void connect(int id) { adj[edge[id].u].push_back(id); adj[edge[id].v].push_back(id); } void dfs(int u, long long k) { int bestV = - 1; vector<int> vtx; FORALL(id, adj[u]) { if (used[id]) continue; used[id]++; int v = edge[id].u + edge[id].v - u; long long w = edge[id].w; depth[v] = depth[u] + 1; dist[v] = dist[u] + w; dfs(v, k); if (bestV == - 1 || _size(st[bestV]) < _size(st[inSt[v]])) bestV = inSt[v]; vtx.push_back(v); } if (bestV == - 1) { inSt[u] = u; st[u].insert({dist[u], depth[u]}); return ; } FORALL(v, vtx) { if (inSt[v] == bestV) continue; FORALL(e, st[inSt[v]]) { auto it = st[bestV].lower_bound({k + dist[u] * 2 - e.fi, 0}); if (it->fi == k + dist[u] * 2 - e.fi) ans = min(ans, e.se + it->se - 2 * depth[u]); } FORALL(e, st[inSt[v]]) { if (e.fi - depth[u] > k) continue; st[bestV].insert(e); } } auto it = st[bestV].lower_bound({k + dist[u], 0}); if (it->fi == k + dist[u]) ans = min(ans, it->se - depth[u]); inSt[u] = bestV; st[bestV].insert({dist[u], depth[u]}); } int best_path(int n, int k, int h[][2], int l[]) { edge.resize(n - 1); adj.resize(n); REP(i, n - 1) { edge[i] = {h[i][0], h[i][1], l[i]}; connect(i); } used.resize(n - 1); depth.resize(n); dist.resize(n); inSt.resize(n); st.resize(n); dfs(0, k); return ans == inf ? - 1 : 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...