Submission #380462

#	Time	Username	Problem	Language	Result	Execution time	Memory
380462		i_am_noob	Designated Cities (JOI19_designated_cities)	C++17	7 / 100	693 ms	76140 KiB

designated_cities

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;

#define ll long long
#define int ll
#define ull unsigned long long
#define ld long double
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
//#define inf 1010000000
#define inf 4000000000000000000
#define eps 1e-9
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
#define ceiling(a,b) (((a)+(b)-1)/(b))
#ifdef i_am_noob
#define bug(...) cerr << "#" << __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 bug(...) 826
#endif

inline char readchar(){
    const int maxn=1000000;
    static char buf[maxn],*p=buf,*q=buf;
    if(p==q&&(q=(p=buf)+fread(buf,1,maxn,stdin))==buf) return EOF;
    else return *p++;
}
inline int readint(){
    int c=readchar(),x=0,neg=0;
    while((c<'0'||c>'9')&&c!='-'&&c!=EOF) c=readchar();
    if(c=='-') neg=1,c=readchar();
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^'0'),c=readchar();
    return neg?-x:x;
}

const int Mod=1000000007,Mod2=998244353;
const int MOD=Mod;
const int maxn=200005;
//i_am_noob
int n,par[maxn],up[maxn],down[maxn],arr[maxn],dp[maxn],dpid[maxn],sumd,sumu,minid,k1,k2,lpos[maxn],rpos[maxn],rev[maxn];
int val[maxn*4],maxid[maxn*4],tag[maxn*4];
int ans[maxn];
vector<pii> adj[maxn];
bool vis[maxn];

void dfs1(int u, int p){
    par[u]=p;
    for(auto& [v,w]: adj[u]){
        if(v==p) up[u]=w,sumu+=w;
        else{
            dfs1(v,u);
            sumd+=w;
            down[v]=w;
        }
    }
}

void dfs2(int u, int p, int curd, int curu){
    arr[u]=0;
    dp[u]=0;
    int cnt=0;
    for(auto& [v,w]: adj[u]) if(v!=p){
        dfs2(v,u,curd+w,curu+up[v]);
        arr[u]+=arr[v]+w;
        cnt++;
        if(dp[v]+w>dp[u]) dp[u]=dp[v]+w,dpid[u]=dpid[v];
    }
    if(!cnt) dpid[u]=u;
    ans[1]=min(ans[1],sumd-curd+curu);
    if(cnt>=2){
        vector<pii> vec;
        for(auto& [v,w]: adj[u]) if(v!=p) vec.pb({dp[v]+w,dpid[v]});
        sort(all(vec));
        reverse(all(vec));
        int tmp=sumd-curd-(vec[0].first+vec[1].first)+curu;
        if(tmp<ans[2]) ans[2]=tmp,minid=u,k1=vec[0].second,k2=vec[1].second;
    }
}

void dfs3(int u, int p, int cur){
    int cnt=0;
    for(auto& [v,w]: adj[u]) if(v!=p) {
        cnt++;
        dfs3(v,u,cur+w);
    }
    if(!cnt) arr[lpos[u]]=cur;
    else arr[lpos[u]]=-inf;
}

void dfs4(int u, int p){
    static int t=0;
    lpos[u]=t++;
    rev[t-1]=lpos[u];
    for(auto& [v,w]: adj[u]) if(v!=p) dfs4(v,u);
    rpos[u]=t-1;
}

void pull(int k){
    val[k]=max(val[k<<1],val[k<<1|1]);
    if(val[k]==val[k<<1]) maxid[k]=maxid[k<<1];
    else maxid[k]=maxid[k<<1|1];
}

void push(int k, int l, int r){
    if(l!=r){
        val[k<<1]+=tag[k],val[k<<1|1]+=tag[k];
        tag[k<<1]+=tag[k],tag[k<<1|1]+=tag[k];
    }
    tag[k]=0;
}

void build(int k, int l, int r){
    if(l==r){
        val[k]=arr[l];
        maxid[k]=l;
        return;
    }
    int mid=l+r>>1;
    build(k<<1,l,mid),build(k<<1|1,mid+1,r);
    pull(k);
}

void modify(int k, int l, int r, int ql, int qr, int x){
    if(ql>r||qr<l) return;
    if(ql<=l&&qr>=r){
        val[k]+=x,tag[k]+=x;
        return;
    }
    int mid=l+r>>1;
    push(k,l,r);
    modify(k<<1,l,mid,ql,qr,x),modify(k<<1|1,mid+1,r,ql,qr,x);
    pull(k);
}

void modify(int u){
    for(int i=u; !vis[i]; i=par[i]){
        bug(i,down[i]);
        vis[i]=1;
        modify(1,0,n-1,lpos[i],rpos[i],-down[i]);
    }
}

signed main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    #ifdef i_am_noob
    freopen("input1.txt","r",stdin);
    freopen("output1.txt","w",stdout);
    freopen("output2.txt","w",stderr);
    #endif
    cin >> n;
    rep(n-1){
        int u,v,w1,w2;
        cin >> u >> v >> w1 >> w2;
        u--,v--;
        adj[u].pb({v,w1}),adj[v].pb({u,w2});
    }
    dfs1(0,-1);
    ans[1]=ans[2]=inf;
    dfs2(0,-1,0,0);
    bug(minid);
    dfs1(minid,-1);
    dfs4(minid,-1);
    dfs3(minid,-1,0);
    vis[minid]=1;
    build(1,0,n-1);
    bug(k1,k2);
    bug(val[1],rev[maxid[1]]);
    modify(k1),modify(k2);
    bug(val[1],rev[maxid[1]]);
    rep2(i,3,n+1){
        if(ans[i-1]==0){
            ans[i]=0;
            continue;
        }
        int u=rev[maxid[1]];
        ans[i]=ans[i-1]-val[1];
        bug(u,val[1]);
        modify(u);
    }
    int q;
    cin >> q;
    while(q--){
        int k;
        cin >> k;
        cout << ans[k] << "\n";
    }
    return 0;
}

Compilation message (stderr)

designated_cities.cpp: In function 'void build(long long int, long long int, long long int)':
designated_cities.cpp:127:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  127 |     int mid=l+r>>1;
      |             ~^~
designated_cities.cpp: In function 'void modify(long long int, long long int, long long int, long long int, long long int, long long int)':
designated_cities.cpp:138:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  138 |     int mid=l+r>>1;
      |             ~^~
designated_cities.cpp: In function 'void modify(long long int)':
designated_cities.cpp:28:18: warning: statement has no effect [-Wunused-value]
   28 | #define bug(...) 826
      |                  ^~~
designated_cities.cpp:146:9: note: in expansion of macro 'bug'
  146 |         bug(i,down[i]);
      |         ^~~
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:28:18: warning: statement has no effect [-Wunused-value]
   28 | #define bug(...) 826
      |                  ^~~
designated_cities.cpp:169:5: note: in expansion of macro 'bug'
  169 |     bug(minid);
      |     ^~~
designated_cities.cpp:28:18: warning: statement has no effect [-Wunused-value]
   28 | #define bug(...) 826
      |                  ^~~
designated_cities.cpp:175:5: note: in expansion of macro 'bug'
  175 |     bug(k1,k2);
      |     ^~~
designated_cities.cpp:28:18: warning: statement has no effect [-Wunused-value]
   28 | #define bug(...) 826
      |                  ^~~
designated_cities.cpp:176:5: note: in expansion of macro 'bug'
  176 |     bug(val[1],rev[maxid[1]]);
      |     ^~~
designated_cities.cpp:28:18: warning: statement has no effect [-Wunused-value]
   28 | #define bug(...) 826
      |                  ^~~
designated_cities.cpp:178:5: note: in expansion of macro 'bug'
  178 |     bug(val[1],rev[maxid[1]]);
      |     ^~~
designated_cities.cpp:28:18: warning: statement has no effect [-Wunused-value]
   28 | #define bug(...) 826
      |                  ^~~
designated_cities.cpp:186:9: note: in expansion of macro 'bug'
  186 |         bug(u,val[1]);
      |         ^~~

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