제출 #333495

#제출 시각아이디문제언어결과실행 시간메모리
333495Aryan_Raina경주 (Race) (IOI11_race)C++14
21 / 100
3072 ms10092 KiB
#include "race.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pii> vii; typedef vector<ll> vll; #define F first #define S second #define PB push_back #define MP make_pair #define INF (1000000009) #define eps (1e-7) #define MOD (1000000007) #define mem(arr, val) memset((arr), (int)(val), sizeof (arr)) #define REP(i, a, b) for (int i=a; i<=b; i++) #define REPn(i, a, b) for (int i=a; i>=b; i--) #define FOR(i, n) REP(i, 0, n-1) #define FORn(j, n) REPn(j, n-1, 0) #define all(v) v.begin(), v.end() #define allR(v) v.rbegin(), v.rend() #define FIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); void dbg_out() { cerr << endl; } template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); } #define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__) const int N=200009; const int K=1000009; int n,k; vector<int> centPar(N); map<int,int> E, tmp; int OneCentroid(int root, vector<vii> &g, vector<bool> &dead) { vi sz(g.size()); function<void (int,int)> get_sz = [&](int u, int par) { sz[u]=1; for (auto v : g[u]) if (v.F!=par&&!dead[v.F]) { get_sz(v.F,u); sz[u]+=sz[v.F]; } }; get_sz(root,-1); int n = sz[root]; function<int (int,int)> dfs = [&](int u, int par) { for (auto v : g[u]) if (v.F!=par&&!dead[v.F]) { if (sz[v.F]>n/2) return dfs(v.F,u); } return u; }; return dfs(root,-1); } int CentroidDecomposition(vector<vii> &g) { vector<bool> dead(g.size(),false); int ans=-1; function<void (int,int,int,int)> dfs = [&] (int u, int par, int len, int wt) { if (wt>k) return; if (tmp.count(wt)) tmp[wt]=min(tmp[wt], len); else tmp[wt]=len; if (E.count(k-wt)) { ans=min(ans,len+E[k-wt]); if (ans==-1) ans=len+E[k-wt]; } for (auto v : g[u]) if (!dead[v.F]&&v.F!=par){ dfs(v.F, u, len+1, wt+v.S); } }; function<void (int)> rec = [&] (int start) { E.clear(); E[0]=0; int c = OneCentroid(start, g, dead); dead[c]=true; for (auto v : g[c]) if (!dead[v.F]) { tmp.clear(); tmp[0]=0; dfs(v.F,c,1,v.S); for (auto itr : tmp) { if (E.count(itr.F)) E[itr.F]=min(E[itr.F], itr.S); else E[itr.F]=itr.S; } } for (auto v : g[c]) if (!dead[v.F]) { rec(v.F); } dead[c]=false; }; rec(0); return ans; } int best_path(int nn, int kk, int h[][2], int l[]) { n=nn, k=kk; vector<vii> g(n); FOR(i,n-1) { g[h[i][0]].PB({h[i][1],l[i]}); g[h[i][1]].PB({h[i][0],l[i]}); } int ans = CentroidDecomposition(g); 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...