Submission #1144844

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144844		shjeong	Designated Cities (JOI19_designated_cities)	C++20	23 / 100	2095 ms	34388 KiB

designated_cities

#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, ll l, ll r){
        prop(node,s,e);
        if(e<l or r<s)return {-1,-1};
        if(l<=s and e<=r)return tree[node];
        ll mid = s+e>>1;
        return max(query(node<<1,s,mid,l,r), query(node<<1|1,mid+1,e,l,r));
    }
};
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-1;
}
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 = 1; v = num = {0};
    memset(vis,0,sizeof vis);
    dfs(c); vis[c] = 1;
    segtree seg(sz(v));
    ll l = sz(v)-1;
    seg.init(1,1,l,v);
    auto [w,idx] = seg.query(1,1,l,1,l);
    cur_sum += w;
    ans[2] = max(ans[2], cur_sum);
    if(sz(adj[c]) != 1){
        int j;
        for(j = num[idx] ; !vis[par[j]] ; j = par[j]);
        for(int j = num[idx] ; !vis[j] ; j = par[j])vis[j] = 1, seg.upd(1,1,l,in[j],out[j],-tmp[j]);
        auto [w2,idx2] = max(seg.query(1,1,l,1,in[j]-1), seg.query(1,1,l,out[j]+1,l));
        assert(w2 > 0);
        cur_sum += w2;
        ans[2] = max(ans[2], cur_sum);
        for(int j = num[idx2] ; !vis[j] ; j = par[j])vis[j] = 1, seg.upd(1,1,l,in[j],out[j],-tmp[j]);
    }
    else for(int j = num[idx] ; !vis[j] ; j = par[j])vis[j] = 1, seg.upd(1,1,l,in[j],out[j],-tmp[j]);
    for(int i = 3 ; i <= l ; i++){
        auto [w,idx] = seg.query(1,1,l,1,l);
        cur_sum += w;
        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; }
    for(int i = 1 ; i <= n ; i++)solve(i);
    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";
    }
}

• Subtask 1: 6 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 9
• Subtask 4: 17 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44