제출 #487965

#제출 시각아이디문제언어결과실행 시간메모리
487965balbitDesignated Cities (JOI19_designated_cities)C++14
100 / 100
729 ms77152 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define int ll #define y1 zck_is_king #define pii pair<int, int> #define ull unsigned ll #define f first #define s second #define ALL(x) x.begin(),x.end() #define SZ(x) (int)x.size() #define SQ(x) (x)*(x) #define MN(a,b) a = min(a,(__typeof__(a))(b)) #define MX(a,b) a = max(a,(__typeof__(a))(b)) #define pb push_back #define REP(i,n) for (int i = 0; i<n; ++i) #define RREP(i,n) for (int i = n-1; i>=0; --i) #define REP1(i,n) for (int i = 1; i<=n; ++i) #define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end())))) #ifdef BALBIT #define IOS() #define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__); template<typename T> void _do(T &&x){cerr<<x<<endl;} template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);} #else #define IOS() ios_base::sync_with_stdio(0);cin.tie(0); #define endl '\n' #define bug(...) #endif const int iinf = 1e9+10; const ll inf = 1ll<<60; const ll mod = 1e9+7 ; void GG(){cout<<"0\n"; exit(0);} ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod ll re=1; while (n>0){ if (n&1) re = re*a %mo; a = a*a %mo; n>>=1; } return re; } ll inv (ll b, ll mo = mod){ if (b==1) return b; return (mo-mo/b) * inv(mo%b,mo) % mo; } const int maxn = 2e5+5; vector<pii> g[maxn]; // to, value int up[maxn], updown[maxn], par[maxn]; ll sigup[maxn]; pii deep[maxn]; // dep, where int dep[maxn]; ll RT = inf; int p1, p2; ll all[maxn], L[maxn], R[maxn]; void dfs1(int v, int p) { par[v] = p; for (pii u : g[v]) { if (u.f != p) { updown[u.f] = u.s; dfs1(u.f, v); } else up[v] = u.s; } } void dfs2(int v, int p) { for (pii u : g[v]) { if (u.f != p) { dep[u.f] = dep[v] + up[u.f]; dfs2(u.f, v); sigup[v] += sigup[u.f] + up[u.f]; } } } void dfs3(int v, int p) { if (p != -1) all[v] = all[p] - up[v] + updown[v]; else all[v] = sigup[v]; vector<pii>here; here.pb({dep[v], v}); for (pii u : g[v]) { if (u.f != p) { dfs3(u.f,v); here.pb(deep[u.f]); } } sort(ALL(here), greater<pii>()); if (SZ(here) > 1) { ll df = all[v] - here[0].f - here[1].f + dep[v]*2; bug(here[0].f, here[1].f, here[0].s, here[1].s); if (df < RT) { RT = df; p1 = here[0].s; p2 = here[1].s; } } deep[v] = here[0]; } pii s[maxn*4]; ll tg[maxn*4]; bool rem[maxn]; void push(int o, int l, int r){ if (tg[o]) { s[o].f += tg[o]; if (l!=r) { tg[o*2] += tg[o]; tg[o*2+1] += tg[o]; } tg[o] = 0; } } void MO(int L, int R, ll v, int o=1, int l=0, int r=maxn-1) { push(o,l,r); if (l>R || r<L) return; if (l >= L && r <= R) { tg[o] += v; push(o,l,r); return; } int mid = (l+r)/2; MO(L,R,v,o*2,l,mid); MO(L,R,v,o*2+1,mid+1,r); s[o] = max(s[o*2], s[o*2+1]); } void MOpt(int p, pii v, int o=1, int l=0, int r=maxn-1) { if (l>p || r<p) return; if (l == r) { s[o] = v; return; } int mid = (l+r)/2; MOpt(p,v,o*2,l,mid); MOpt(p,v,o*2+1,mid+1,r); s[o] = max(s[o*2], s[o*2+1]); } int IT = 0; void dfs4(int v, int p) { L[v] = R[v] = IT++; for (pii u : g[v]) { if (u.f != p) { dfs4(u.f,v); R[v] = R[u.f]; } } } ll ans[maxn]; void clr(int v) { while (!rem[v]) { rem[v] = 1; int p = par[v]; MO(L[v], R[v], -up[v]); v = p; } } signed main(){ IOS(); int n; cin>>n; REP(i,n-1) { int a,b,c,d; cin>>a>>b>>c>>d; swap(c,d); g[a].pb({b,c}); g[b].pb({a,d}); } dfs1(1,-1); dfs2(1,-1); dfs3(1,-1); memset(ans, 0x3f, sizeof ans); REP1(i,n) { bug(i, up[i], dep[i], sigup[i], all[i]); MN(ans[1], all[i]); } bug(RT, p1, p2); ans[2] = RT; dep[p1] = up[p1] = 0; dfs1(p1, -1); dfs2(p1, -1); dfs4(p1, -1); rem[p1] = 1; REP1(i,n) { bug(i, L[i], dep[i], up[i]); MOpt(L[i], {dep[i], i}); } bug(s[1].f, s[1].s, dep[p2]); clr(p2); for (int k = 3; k<=n; ++k) { pii hi = s[1]; bug (hi.f, hi.s); RT -= hi.f; clr(hi.s); ans[k] = RT; } int qq; cin>>qq; while (qq--) { int x; cin>>x; cout<<ans[x]<<endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...