Submission #1266212

#TimeUsernameProblemLanguageResultExecution timeMemory
1266212WH8경주 (Race) (IOI11_race)C++20
100 / 100
292 ms99472 KiB
#include "race.h" #include <bits/stdc++.h> using namespace std; #define iloop(x, n) for (long long i = x; i < n; ++i) #define jloop(x, n) for (long long j = x; j < n; ++j) #define kloop(x, n) for (long long k = x; k < n; ++k) #define dloop(x, n) for (long long d = x; d >= n; --d) #define int long long #define pll pair<long long, long long> #define pii pair<int, int> #define iii tuple<int, int, int> #define vi vector<int> #define mp make_pair #define pb push_back #define f first #define s second #define endl '\n' #define g0(a) get<0>(a) #define g1(a) get<1>(a) #define g2(a) get<2>(a) #define g3(a) get<3>(a) #define dg(x) cerr << #x << ": " << x << endl #define all(x) x.begin(), x.end() #define FASTIO \ ios::sync_with_stdio(false); \ cin.tie(0); \ cout.tie(0); int n, k; vector<vector<pll>> al(200005); int ans = 1e15; int os[200005]; vector<multiset<pll>> mem(200005); int depth[200005]; int pd[200005]; void dfs(int x, int p){ multiset<pll> bs, ss; int bso = 0, sso = 0; bs.insert({0, depth[x]}); for (pll ed : al[x]){ int it = ed.f; if (it == p) continue; dfs(it, x); } //cout << "WE ARE AT " << x << endl; for (pll ed: al[x]){ int it = ed.f; if (it == p) continue; ss.swap(mem[it]); sso = os[it]; if (ss.size() > bs.size()) { bs.swap(ss); swap(bso, sso); } //dg(x); //dg(it); /*cout << "SS : " ; for (auto it : ss){ cout << "{ " << it.f << ", " << it.s << " } "; } cout << endl; cout << "BS : " ; for (auto it : bs ){ cout << "{ " << it.f << ", " << it.s << " } "; } cout << endl;*/ for (auto cand : ss){ // length, endpoint int tar = (k - (sso + cand.f)) - bso; auto itr = bs.lower_bound({tar, -1e15}); if (itr != bs.end() and (*itr).f == tar){ int neu = (*itr).s + cand.s - 2 * depth[x]; if (neu > 0) ans = min(ans, neu); } } for (auto cand : ss){ // add to big set, negating offset bs.insert({cand.f + sso - bso, cand.s}); } } /*cout << "BS AFTER: " ; for (auto it : bs){ cout << "{ " << it.f << ", " << it.s << " } "; } cout << endl;*/ os[x] = bso + pd[x]; mem[x].swap(bs); } void ddfs(int x, int p){ for (auto it : al[x]){ if (it.f == p) continue; depth[it.f] = depth[x] + 1; pd[it.f] = it.s; ddfs(it.f, x); } } int32_t best_path(int32_t N, int32_t K, int32_t H[][2], int32_t L[]) { n = N, k = K; iloop(0, n-1){ int a = H[i][0], b = H[i][1]; int c = L[i]; al[a].pb({b, c}); al[b].pb({a, c}); } ddfs(0, -1); dfs(0, -1); /*cout << "DEPTH\n"; iloop(0, n) cout << depth[i] << " "; cout << "PD\n"; iloop(0, n) cout << pd[i] << " ";*/ return (ans == 1e15 ? -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...