제출 #624435

#제출 시각아이디문제언어결과실행 시간메모리
624435radalDesignated Cities (JOI19_designated_cities)C++17
16 / 100
621 ms69516 KiB
#include <bits/stdc++.h> #pragma GCC target("sse,sse2,avx2") #pragma GCC optimize("unroll-loops,O2") #define rep(i,l,r) for (int i = l; i < r; i++) #define repr(i,r,l) for (int i = r; i >= l; i--) #define X first #define Y second #define all(x) (x).begin() , (x).end() #define pb push_back #define endl '\n' #define debug(x) cerr << #x << " : " << x << endl; using namespace std; typedef long long ll; typedef long double ld; typedef pair<int,int> pll; constexpr ll N = 2e5+10,mod = 998244353,inf = 1e9+10,lg = 20; inline int mkay(int a,int b){ if (a+b >= mod) return a+b-mod; if (a+b < 0) return a+b+mod; return a+b; } inline int poww(int a,int k){ if (k < 0) return 0; int z = 1; while (k){ if (k&1) z = 1ll*z*a%mod; a = 1ll*a*a%mod; k /= 2; } return z; } int par[N][lg],h[N],r,U,V,sz[N],tin[N],T,lc; ll opt[N],d[N][2],up[N],sum,lz[N*4]; pair<ll,int> mx[N],seg[N*4]; vector<int> ti; vector<pair<int,pll>> adj[N]; void pre(int v,int p){ par[v][0] = p; tin[v] = T++; ti.pb(v); sz[v] = 1; for (auto u : adj[v]){ if (u.X == p) continue; h[u.X] = h[v]+1; d[u.X][0] = d[v][0]+u.Y.X; d[u.X][1] = d[v][1]+u.Y.Y; pre(u.X,v); up[v] += up[u.X]+u.Y.Y; sz[v] += sz[u.X]; } } void dfs(int v,int p){ if (adj[v].size() == 1){ mx[v] = {d[v][0],v}; return; } ll a = -1,b = -1; pll pa = {-1,-1}; for (auto u : adj[v]){ if (u.X == p) continue; dfs(u.X,v); mx[v] = max(mx[v],mx[u.X]); if (mx[u.X].X > a){ swap(pa.X,pa.Y); b = a; a = mx[u.X].X; pa.X = mx[u.X].Y; } else if (mx[u.X].X > b){ b = mx[u.X].X; pa.Y = mx[u.X].Y; } } if (b == -1) return; ll calc = sum-up[r]+d[v][1]-d[v][0]-a-b+2*d[v][0]; if (calc < opt[2]){ opt[2] = calc; U = pa.X; V = pa.Y; lc = v; } } int lca(int u,int v){ if (h[u] < h[v]) swap(u,v); repr(i,lg-1,0){ if ((1 << i) <= h[u]-h[v]) u = par[u][i]; } if (v == u) return v; repr(i,lg-1,0){ if (par[v][i] != par[u][i]){ v = par[v][i]; u = par[u][i]; } } return par[v][0]; } void build(int l,int r,int v = 1){ if (r-l == 1){ int u = ti[l]; if (u == U || u == V || adj[u].size() != 1){ seg[v] = {0,u}; return; } int lc2 = lca(lc,u); if (lc2 != lc){ seg[v] = {d[u][0]-d[lc2][0]+d[lc][1]-d[lc2][1],u}; return; } lc2 = lca(u,U); if (lc2 == lc) lc2 = lca(u,V); seg[v] = {d[u][0]-d[lc2][0],u}; return; } int m = (l+r) >> 1,u = (v << 1); build(l,m,u); build(m,r,u|1); seg[v] = max(seg[u],seg[u|1]); } void upd(int l,int r,int s,int e,ll x,int v = 1){ if (s == l && r == e){ seg[v].X += x; lz[v] += x; return; } int m = (l+r) >> 1,u = (v << 1); if (lz[v]){ seg[u].X += lz[v]; seg[u|1].X += lz[v]; lz[u] += lz[v]; lz[u|1] += lz[v]; lz[v] = 0; } if (e <= m){ upd(l,m,s,e,x,u); seg[v] = max(seg[u],seg[u|1]); return; } if (s >= m){ upd(m,r,s,e,x,u|1); seg[v] = max(seg[u],seg[u|1]); return; } upd(l,m,s,m,x,u); upd(m,r,m,e,x,u|1); seg[v] = max(seg[u],seg[u|1]); } int32_t main(){ ios :: sync_with_stdio(0); cin.tie(0); memset(opt,63,sizeof opt); int n; cin >> n; rep(i,1,n){ int u,v,a,b; cin >> u >> v >> a >> b; adj[u].pb({v,{a,b}}); adj[v].pb({u,{b,a}}); sum += a; sum += b; } if (n == 2){ int q; cin >> q; while (q--){ int t; cin >> t; if (t == 2){ cout << 0 << endl; continue; } if (t == 1){ cout << min(adj[1][0].Y.Y,adj[1][0].Y.X) << endl; continue; } } return 0; } rep(i,1,n+1) if (adj[i].size() > 1) r = i; pre(r,0); rep(j,1,lg){ rep(i,1,n+1){ par[i][j] = par[par[i][j-1]][j-1]; } } int leaf = 0; rep(i,1,n+1){ opt[1] = min(opt[1],sum-up[r]+d[i][1]-d[i][0]); leaf += (adj[i].size() == 1); } dfs(r,0); set<int> st; st.insert(tin[U]); st.insert(tin[V]); int q; cin >> q; build(0,n); rep(i,3,leaf){ pair<ll,int> p = seg[1]; int v = seg[1].Y; upd(0,n,tin[v],tin[v]+1,-p.X); opt[i] = opt[i-1]-p.X; int lc2 = lca(v,lc); if (lc2 != lc){ st.insert(tin[v]); int cur = par[lc][0],perv = lc; while (perv != lc2){ upd(0,n,tin[cur],tin[cur]+sz[cur],-(d[lc][1]-d[cur][1])); upd(0,n,tin[perv],tin[perv]+sz[perv],d[lc][1]-d[cur][1]); perv = cur; cur = par[cur][0]; } if (lc2 != r){ upd(0,n,0,n,-(d[lc][1]-d[lc2][1])); upd(0,n,tin[lc2],tin[lc2]+sz[lc2],d[lc][1]-d[lc2][1]); } lc = lc2; continue; } auto it = st.lower_bound(tin[v]); int lc3 = -1; if (it != st.end()){ int u = ti[*it]; lc2 = lca(v,u); } if (it != st.begin()){ it--; int u = ti[*it]; lc3= lca(u,v); } if (lc3 != -1 && h[lc3] > h[lc2]) swap(lc3,lc2); st.insert(tin[v]); int cur = par[v][0]; while(cur != lc2){ upd(0,n,tin[cur],tin[cur]+sz[cur],-(d[cur][0]-d[par[cur][0]][0])); cur = par[cur][0]; } } while (q--){ int t; cin >> t; if (t >= leaf){ cout << 0 << endl; continue; } cout << opt[t] << endl; } return 0; }
#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...