Submission #1144839

#TimeUsernameProblemLanguageResultExecution timeMemory
1144839shjeongDesignated Cities (JOI19_designated_cities)C++20
0 / 100
146 ms34280 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #pragma optimize("unroll-loops") #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define all(x) x.begin(), x.end() #define rll(x) x.rbegin(), x.rend() #define COMP(x) x.erase(unique(all(x)), x.end()) #define MOD 1000000007 #define MOD2 998244353 #define sz(x) (ll)x.size() typedef __int128_t lll; typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<ll,ll> pi; typedef pair<ll, pi> PP; const ll Lnf = 2e18; const ll inf = 1e9; ll n, q; struct segtree{ vector<pi> tree; vector<ll> lazy; ll n; segtree(ll sz){ n=sz; tree.resize(sz*4); lazy.resize(sz*4); } void prop(ll node, ll s, ll e){ if(!lazy[node])return; tree[node].first += lazy[node]; if(s^e)lazy[node<<1]+=lazy[node],lazy[node<<1|1]+=lazy[node]; lazy[node]=0; } void init(ll node, ll s, ll e, vector<ll> &v){ if(s==e)tree[node] = {v[s],s}; else{ ll mid = s+e>>1; init(node<<1,s,mid,v); init(node<<1|1,mid+1,e,v); tree[node] = max(tree[node<<1],tree[node<<1|1]); } } void upd(ll node, ll s, ll e, ll l, ll r, ll d){ prop(node,s,e); if(e<l or r<s)return; if(l<=s and e<=r){ lazy[node] = d; prop(node,s,e); return; } ll mid = s+e>>1; upd(node<<1,s,mid,l,r,d); upd(node<<1|1,mid+1,e,l,r,d); tree[node] = max(tree[node<<1], tree[node<<1|1]); } pi query(ll node, ll s, ll e){ prop(node,s,e); return tree[node]; } }; ll in[202020], out[202020]; ll ans[202020]; vector<array<ll,3>> adj[202020]; ll siz[202020]; ll cur_sum = 0, cnt = 0; ll par[202020], tmp[202020]; vector<ll> v = {0}, num = {0}; bool vis[202020]; void dfs(ll x, ll sum=0, ll prv=-1){ bool flag = 0; in[x] = cnt; for(auto [next,w1,w2] : adj[x])if(prv!=next){ cur_sum += w2; par[next] = x; tmp[next] = w1; flag = 1; dfs(next,sum+w1,x); } if(!flag){ in[x] = ++cnt; out[x] = cnt; v.push_back(sum); num.push_back(x); } else out[x] = cnt; } void sol1(ll x, ll prv=-1){ for(auto [next,w1,w2] : adj[x])if(prv!=next){ cur_sum += w2; sol1(next,x); } } void sol11(ll x, ll prv=-1){ ans[1] = max(ans[1], cur_sum); for(auto [next,w1,w2] : adj[x])if(prv!=next){ cur_sum -= w2; cur_sum += w1; sol11(next,x); cur_sum -= w1; cur_sum += w2; } } void solve(ll c){ cur_sum = 0, cnt = 0; v = num = {0}; dfs(c); vis[c] = 1; segtree seg(sz(v)); ll l = sz(v)-1; seg.init(1,1,l,v); if(num[1] != c)for(int i = 1 ; i <= l ; i++){ auto [w,idx] = seg.query(1,1,l); assert(w>0); cur_sum += w; if(i==1)ans[2] = max(ans[2], cur_sum); else ans[i] = max(ans[i],cur_sum); for(int j = num[idx] ; !vis[j] ; j = par[j])vis[j] = 1, seg.upd(1,1,l,in[j],out[j],-tmp[j]); } } int main(){ fast; ll sum = 0; cin>>n; for(int i = 0 ; i < n-1 ; i++){ ll a,b,c,d; cin>>a>>b>>c>>d; adj[a].push_back({b,c,d}); adj[b].push_back({a,d,c}); sum += c+d; } sol1(1); sol11(1); ll c = 1; for(int i = 1 ; i <= n ; i++)if(sz(adj[i]) != 1){ c=i; break; } solve(c); for(int i = 2 ; i <= n ; i++)ans[i]=max(ans[i],ans[i-1]); cin>>q; while(q--){ ll a; cin>>a; cout<<sum-ans[a]<<"\n"; } }
#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...