제출 #487452

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
487452		phamhoanghiep	Designated Cities (JOI19_designated_cities)	C++17	100 / 100	919 ms	96600 KiB

designated_cities

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define int long long
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
const int maxn=2e5+5;
vector<iii> AdjList[maxn];
int n;
int cost[maxn];
int res[maxn];
int sum;
int ans[maxn];
int ans1[maxn];
int path[maxn];
bool used[maxn];
pair<int,int> par[maxn];
void prep(int s=1, int p=-1) {
    ////cout<<"prep "<<s<<endl;
    for(iii tmp: AdjList[s]) {
        int u=tmp.fi;
        if(u==p) continue;
        int w=tmp.se.se;
        cost[1]+=w;
        prep(u,s);
    }
}
void dfs(int s=1, int p=-1) {
    ////cout<<"dfs "<<s<<endl;
    for(iii tmp: AdjList[s]) {
        int u=tmp.fi;
        if(u==p) continue;
        int fw=tmp.se.fi;
        int bw=tmp.se.se; // currently bw
        cost[u]=cost[s]+fw-bw;
        dfs(u,s);
    }
}
int in[maxn];
int out[maxn];
int rev[maxn];
int up[maxn][20];
int curt=0;
bool ancestor(int a, int b) {
    if(!a) return true;
    if(!b) return false;
    return in[a]<=in[b]&&out[a]>=out[b];
}
void dfs2(int s, int p=0) {
    ////cout<<"dfs2 "<<s<<endl;
    in[s]=++curt;
    //cout<<"in "<<s<<" = "<<in[s]<<endl;
    rev[in[s]]=s;
    up[s][0]=p;
    for(int i=1 ; i<20 ; i++) {
        up[s][i]=up[up[s][i-1]][i-1];
        ////cout<<"up "<<s<<" "<<i<<" = "<<up[s][i]<<endl;
    }
    for(iii tmp: AdjList[s]) {
        int u=tmp.fi;
        if(u==p) continue;
        int fw=tmp.se.fi;
        path[u]=path[s]+fw;
        par[u]=ii(s,fw);
        ////cout<<"par "<<u<<" = "<<s<<" "<<fw<<endl;
        ////cout<<"u = "<<u<<endl;
        dfs2(u,s);
    }
    out[s]=curt;
    //cout<<"out "<<s<<" = "<<out[s]<<endl;
}
int lca(int u, int v) {
    ////cout<<"lca "<<u<<" "<<v<<" = "<<endl;
    if(ancestor(u,v)) return u;
    if(ancestor(v,u)) return v;
    for(int i=20 ; i>0 ; i--) {
        ////cout<<"up "<<u<<" "<<i<<" = "<<up[u][i]<<endl;
        if(!ancestor(up[u][i],v)) u=up[u][i];
    }
    ////cout<<up[u][0]<<endl;
    return up[u][0];
}
// segment tree
pair<int,int> st[maxn*4]; // max
int lz[maxn*4];
void build(int id=1, int tl=1, int tr=n) {
    ////cout<<"build "<<tl<<" "<<tr<<endl;
    if(tl==tr) {
        st[id]=make_pair(path[rev[tl]],tl);
        lz[id]=0;
        ////cout<<"st "<<id<<" = "<<st[id].first<<" "<<st[id].second<<'\n';
        return;
    }
    int mid=(tl+tr)/2;
    build(id*2,tl,mid);
    build(id*2+1,mid+1,tr);
    lz[id]=0;
    st[id]=max(st[id*2],st[id*2+1]);
    ////cout<<"st "<<tl<<" "<<tr<<" = "<<st[id].first<<" "<<st[id].second<<'\n';
}
void do_lazy(int id, int tl, int tr) {
    if(!lz[id]) return;
    if(tl!=tr) {
        lz[id*2]+=lz[id];
        lz[id*2+1]+=lz[id];
    }
    st[id].first-=lz[id];
    lz[id]=0;
    return;
}
void upd(int id, int tl, int tr, int l, int r, int sub) {
    ////cout<<"update "<<id<<" "<<tl<<" "<<tr<<" "<<l<<" "<<r<<endl;
    do_lazy(id,tl,tr);
    if(tl>r||tr<l) return;
    if(l<=tl&&tr<=r) {
        lz[id]+=sub;
        do_lazy(id,tl,tr);
        return;
    }
    int mid=(tl+tr)/2;
    upd(id*2,tl,mid,l,r,sub);
    upd(id*2+1,mid+1,tr,l,r,sub);
    st[id]=max(st[id*2],st[id*2+1]);
    ////cout<<"st "<<tl<<" "<<tr<<" = "<<st[id].first<<" "<<st[id].second<<endl;
}
void sub(int v) {
    while(v) {
        ii tmp=par[v];
        int w=tmp.second;
        int p=tmp.first;
        if(used[v]) break;
        used[v]=1;
        upd(1,1,n,in[v],out[v],w);
        //cout<<"update "<<v<<" "<<w<<endl;
        v=p;
    }
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i=1 ; i<n ; i++) {
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        AdjList[a].push_back(iii(b,ii(c,d))); // forward then backward
        AdjList[b].push_back(iii(a,ii(d,c)));
        sum+=c; sum+=d;
    }
    prep(); dfs();
    int root=1;
    int mx_cost=cost[1];
    for(int i=2 ; i<=n ; i++) {
        if(cost[i]>mx_cost) {
            root=i;
            mx_cost=cost[i];
        }
    }
    dfs2(root);
    ////cout<<"root = "<<root<<endl;
    build();
    ////cout<<"cost "<<root<<" = "<<cost[root]<<endl;
    pair<int,int> mn=st[1];
    int id1=mn.second;
    int val1=mn.first;
    int root1=rev[id1];
    curt=0;
    par[root]=ii(0,0);
    path[root]=0;
    dfs2(root);
    build();
    ans[1]=cost[root];
    //cout<<"root = "<<root<<endl;
    //cout<<"sum = "<<sum<<endl;
    //cout<<"ans "<<1<<" = "<<ans[1]<<endl;
    for(int i=1 ; i<=n ; i++) used[i]=0;
    for(int i=2 ; i<=n ; i++) {
        pair<int,int> mn=st[1];
        int id=mn.second;
        int val=mn.first;
        int v=rev[id];
        //cout<<"val "<<val<<endl;
        //cout<<"v = "<<v<<endl;
        ////cout<<endl<<"v = "<<v<<endl;
        ////cout<<"mn = "<<val<<" "<<id<<endl;
        ans[i]=ans[i-1]+val;
        //cout<<"ans "<<i<<" = "<<ans[i]<<endl<<endl;
        sub(v);
    }
    curt=0;
    par[root1]=ii(0,0);
    path[root1]=0;
    dfs2(root1);
    build();
    ans1[1]=cost[root1];
    //cout<<"root = "<<root<<endl;
    //cout<<"sum = "<<sum<<endl;
    //cout<<"ans "<<1<<" = "<<ans[1]<<endl;
    for(int i=1 ; i<=n ; i++) used[i]=0;
    for(int i=2 ; i<=n ; i++) {
        pair<int,int> mn=st[1];
        int id=mn.second;
        int val=mn.first;
        int v=rev[id];
        //cout<<"val "<<val<<endl;
        //cout<<"v = "<<v<<endl;
        ////cout<<endl<<"v = "<<v<<endl;
        ////cout<<"mn = "<<val<<" "<<id<<endl;
        ans1[i]=ans1[i-1]+val;
        //cout<<"ans "<<i<<" = "<<ans[i]<<endl<<endl;
        sub(v);
    }
    int q;
    cin>>q;
    while(q--) {
        int x;
        cin>>x;
        ans[x]=max(ans[x],ans1[x]);
        cout<<sum-ans[x]<<'\n';
    }
}

컴파일 시 표준 에러 (stderr) 메시지

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:165:9: warning: unused variable 'val1' [-Wunused-variable]
  165 |     int val1=mn.first;
      |         ^~~~

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