제출 #1277427

#제출 시각아이디문제언어결과실행 시간메모리
1277427nhmktu경주 (Race) (IOI11_race)C++17
0 / 100
3093 ms3128 KiB
#include <bits/stdc++.h> #define ll long long #define FOR(i,a,b) for(int i=a;i<=b;i++) #define ROF(i,a,b) for(int i=a;i>=b;i--) #define pi pair<int,int> #define pii pair<int,pi> #define fi first #define se second #define pb push_back #define all(x) x.begin(), x.end() #define sz(a) (int) a.size() #define endl '\n' #define data "data" using namespace std; const ll linf = 1e18; const int inf = 1e9; const int MOD = 1e9 + 7, M = 1e5; const int MX = 1e6; void add(int &a, int b) { a += b; if(a>=MOD) a-=MOD; if(a<0) a += MOD; } int modulo(int x) { if(x<=1) return 1; return (MOD - MOD/x) * modulo(MOD/x) % MOD; } int mul(int a, int b) { return (1ll *a%MOD * b%MOD) % MOD; } int ans = inf; int n, k; int mn[MX+3]; int Sz[M+3]; bool iscent[M+3]; vector<pi> adj[M+3]; void dfs(int u, int p) { Sz[u] = 1; FOR(i, 0, sz(adj[u]) -1) { int v = adj[u][i].fi; if(v == p || iscent[v]) continue; dfs(v, u); Sz[u] += Sz[v]; } } int find_cent(int u, int tree_sz, int p) { FOR(i, 0, sz(adj[u]) -1) { int v = adj[u][i].fi; if(v == p || iscent[v] || Sz[v] * 2 < tree_sz) return find_cent(v, tree_sz, u); } return u; } void compute(int u, int dept, bool f, int sum, int p) { if(f == 1) { ans = max(ans, mn[k - sum] + dept); } else { mn[sum] = min(mn[sum], dept); } FOR(i, 0, sz(adj[u]) -1) { int v = adj[u][i].fi, w = adj[u][i].se; if(iscent[v] || v == p) continue; compute(v, dept + 1, f, sum + w, u); } } void Erase(int u, int dept, int sum, int p) { mn[sum] = inf; FOR(i, 0, sz(adj[u]) -1) { int v = adj[u][i].fi, w = adj[u][i].se; if(iscent[v] || v == p) continue; Erase(v, dept + 1, sum + w, u); } } void build_cent(int u) { dfs(u, -1); int cur = find_cent(u, Sz[u], u); iscent[cur] = 1; FOR(i, 0, sz(adj[cur]) -1) { int v = adj[cur][i].fi, w = adj[cur][i].se; if(iscent[v]) continue; compute(v, 1, 1, w, cur); compute(v, 1, 0, w, cur); } FOR(i, 0, sz(adj[cur]) -1) { int v = adj[cur][i].fi, w = adj[cur][i].se; if(iscent[v]) continue; Erase(v, 1, w, u); } FOR(i, 0, sz(adj[cur]) -1) { int v = adj[cur][i].fi; if(iscent[v]) continue; build_cent(v); } } void solve(void) { FOR(i, 0, M) mn[i] = inf; build_cent(1); } int best_path(int N, int K, int H[][2], int L[]) { n = N; k = K; FOR(i, 0, n - 2) { int u = H[i][0] + 1; int v = H[i][1] + 1; adj[u].pb({v, L[i]}); adj[v].pb({u, L[i]}); } solve(); 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...