Submission #769915

#TimeUsernameProblemLanguageResultExecution timeMemory
769915ByeWorldRace (IOI11_race)C++14
100 / 100
352 ms98828 KiB
#include <bits/stdc++.h> #include "race.h" #define fi first #define se second #define pb push_back #define ll long long using namespace std; typedef pair<ll,ll> pii; typedef pair<ll, pii> ipii; const ll MAXN = 2e5+10; const ll INF = 2e18; const ll MOD = 1e9+7; ll n, k; vector <pii> adj[MAXN]; ll sub[MAXN], big[MAXN], dep[MAXN], off[MAXN]; ll ans = INF; map <ll, ll> *m[MAXN]; void dfs(ll nw, ll par){ sub[nw] = 1; dep[nw] = dep[par]+1; big[nw] = n+1; for(auto ed : adj[nw]){ ll nx = ed.fi; if(nx == par) continue; dfs(nx, nw); if(sub[nx] > sub[big[nw]]) big[nw] = nx; sub[nw] += sub[nx]; } } void upd(ll nw, ll len, ll depth){ if((*m[nw]).find(len) == (*m[nw]).end()) (*m[nw])[len] = depth; else (*m[nw])[len] = min((*m[nw])[len], depth); } void dsu(ll nw, ll par){ if(adj[nw].size() == 1 && par != 0){ //leaf m[nw] = new map<ll,ll>; upd(nw, 0, dep[nw]); return; } for(auto ed : adj[nw]){ ll nx = ed.fi; ll wei = ed.se; if(nx == par) continue; dsu(nx, nw); //dfs off[nx] += wei; //nambah edge } m[nw] = m[big[nw]]; off[nw] = off[big[nw]]; //offset + map sama upd(nw, -off[nw], dep[nw]); for(auto ed : adj[nw]){ ll nx = ed.fi; ll wei = ed.se; if(nx == par || nx == big[nw]) continue; // cek inside for(auto in : (*m[nx])){ ll len = in.fi; ll depth = in.se; len += off[nx]; //keluar, nambahin if(len > k || (*m[nw]).find(k-len-off[nw]) == (*m[nw]).end() ) continue; //gk ad ans = min(ans, (*m[nw])[k-len-off[nw]] + depth - 2*dep[nw]); //cek dalem, kurangin } // merge (*m[nx]) for(auto in : (*m[nx])){ ll len = in.fi; ll depth = in.se; len += off[nx]; if( (*m[nw]).find(len-off[nw]) == (*m[nw]).end() ) (*m[nw])[len-off[nw]] = depth; else (*m[nw])[len-off[nw]] = min((*m[nw])[len-off[nw]], depth); } } // cout << nw << ' ' << off[nw] << "off\n"; // for(auto in : (*m[nw])){ // cout << in.fi << ' '<< in.se << '\n'; // } //cek dalem if( (*m[nw]).find(k-off[nw]) != (*m[nw]).end() ) ans = min(ans, (*m[nw])[k-off[nw]] - dep[nw]); } int best_path(int N, int K, int H[][2], int L[]){ n = N; k = K; for(ll i=0; i<n-1; i++){ adj[H[i][0]+1].pb({H[i][1]+1, L[i]}); adj[H[i][1]+1].pb({H[i][0]+1, L[i]}); } // 1-n dfs(1, 0); dsu(1, 0); return (ans==INF ? -1 : ans); }

Compilation message (stderr)

race.cpp: In function 'void dsu(long long int, long long int)':
race.cpp:51:21: warning: unused variable 'wei' [-Wunused-variable]
   51 |   ll nx = ed.fi; ll wei = ed.se;
      |                     ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...