제출 #887525

#제출 시각아이디문제언어결과실행 시간메모리
887525BBart888경주 (Race) (IOI11_race)C++14
43 / 100
3090 ms99732 KiB
#include <cstdio> #include <iostream> #include <vector> #include <list> #include <string> #include <set> #include <map> #include <algorithm> #include <fstream> #include <cmath> #include <queue> #include <stack> #include <cassert> #include <cstring> #include <climits> #include <functional> #include<cstdlib> //#include "arc.h" //#include "dreaming.h" using namespace std; typedef pair<int, int> PII; typedef vector<int> VI; typedef long long LL; const int MAXN = 2e5 + 11; using ll = long long; const ll mod1 = 1e9 + 7; const ll mod2 = 1000000021; const ll P = 31; /* void setIO(string name = "") { cin.tie(0)->sync_with_stdio(0); // see /general/fast-io if ((name.size())) { freopen((name + ".in").c_str(), "r", stdin); // see /general/input-output freopen((name + ".out").c_str(), "w", stdout); } } */ vector<pair<int,ll>> adj[MAXN]; ll n, k; int sz[MAXN]; bool vis[MAXN]; map<ll, ll> mp; vector<ll> to_del; map<ll, bool> used; ll ans = 1e9; void dfs(int v, int p,bool fill,ll sum,ll len) { if (sum > k) return; if (fill) { to_del.push_back(sum); if (used[sum] == 0) mp[sum] = len, used[sum] = true; else mp[sum] = min(mp[sum], len); } else { ll need = k - sum; //cout << v << " " << sum << " " << len << // " and " << need << " " << mp[need] << '\n'; if (need == 0 || mp[need] != 0) ans = min(ans, mp[need] + len); } for (auto u : adj[v]) { if (u.first == p || vis[u.first]) continue; dfs(u.first, v, fill, sum + u.second, len + 1); } } int find_size(int v, int p) { if (vis[v]) return 0; sz[v] = 1; for (auto u : adj[v]) { if (u.first == p) continue; sz[v] += find_size(u.first, v); } return sz[v]; } int find_centroid(int v, int p,int n) { for (auto u : adj[v]) { if (u.first == p || vis[u.first]) continue; if (sz[u.first] > n / 2) return find_centroid(u.first, v, n); } return v; } void decomp(int v, int p) { find_size(v, -1); int c = find_centroid(v, -1, sz[v]); vis[c] = true; to_del.clear(); for (auto u : adj[c]) { if (vis[u.first]) continue; dfs(u.first, -1, 0, u.second, 1); dfs(u.first, -1, 1, u.second, 1); } for (auto vals : to_del) { mp[vals] = 0; used[vals] = false; } for (auto u : adj[c]) { if (vis[u.first]) continue; decomp(u.first, c); } } int best_path(int _n, int _k, int h[][2], int l[]) { n = _n; k = _k; for (int i = 0; i < n - 1; i++) { int v = h[i][0]+1; int u = h[i][1]+1; int cost = l[i]; adj[u].push_back({ v,cost }); adj[v].push_back({ u,cost }); } decomp(1, -1); if (ans == 1e9) ans = -1; return ans; } /* int main() { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false); //setIO("movie"); cin >> n >> k; for(int i =1;i<n;i++) { int a, b, c; cin >> a >> b >> c; adj[a].push_back({ b,c }); adj[b].push_back({ a,c }); } decomp(1, -1); if (ans == 1e9) cout << -1 << '\n'; else cout << ans << '\n'; 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...