제출 #1053283

#제출 시각아이디문제언어결과실행 시간메모리
1053283vincentbucourt1경주 (Race) (IOI11_race)C++14
43 / 100
171 ms81236 KiB
#include "race.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define f first #define s second const static ll INF = 1e18; const ll MAXN = 200001; static ll N, sumNeed; static vector<pair<ll, ll>> adj[MAXN]; static int depth[MAXN], sum[MAXN]; static map<ll, ll> maps[MAXN]; static ll ans = INF; void dfs (ll node = 0, ll parent = -1) { maps[node][sum[node]] = depth[node]; for (pair<ll, ll> nxt : adj[node]) { ll nodenxt = nxt.f, weightnxt = nxt.s; if (nodenxt == parent) continue; depth[nodenxt] = depth[node] + 1; sum[nodenxt] = sum[node] + weightnxt; dfs(nodenxt, node); if (maps[nodenxt].size() > maps[node].size()) swap(maps[nodenxt], maps[node]); for (pair<ll, ll> elem : maps[nodenxt]) { ll sumOn = elem.f, depthOn = elem.s; ll need = -sumOn + 2*sum[node] + sumNeed; if (maps[node].find(need) != maps[node].end()) { ans = min(ans, maps[node][need] - 2*depth[node] + depthOn); } if (maps[node].find(sumOn) == maps[node].end()) { maps[node][sumOn] = depthOn; } else { maps[node][sumOn] = min(maps[node][sumOn], depthOn); } } maps[nodenxt].clear(); } } int best_path(int N, int K, int H[][2], int L[]) { ::N = N; sumNeed = K; for (int i = 0; i < N-1; i++) { adj[H[i][0]].push_back({H[i][1], L[i]}); adj[H[i][1]].push_back({H[i][0], L[i]}); } dfs(); if (ans == INF) return -1; else return 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...