Submission #708864

#	Time	Username	Problem	Language	Result	Execution time	Memory
708864		alvingogo	Designated Cities (JOI19_designated_cities)	C++14	100 / 100	519 ms	70760 KiB

designated_cities

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
#define int long long
using namespace std;

struct no{
    vector<pair<int,pair<int,int> > > ch;
    int sum=0;
    int sum2=0;
    pair<int,int> dp={0,-1},dp2={0,-1};
};
int n;
int zz=0;
vector<no> v;
vector<int> ans;
void dfs(int r,int f){
    for(auto h:v[r].ch){
        if(h.fs!=f){
            dfs(h.fs,r);
            v[r].sum+=v[h.fs].sum+h.sc.sc;
        }
    }
}
void dfs2(int r,int f,int z=0){
    v[r].sum+=z;
    ans[1]=max(ans[1],v[r].sum);
    for(auto h:v[r].ch){
        if(h.fs!=f){
            dfs2(h.fs,r,h.sc.fs+v[r].sum-v[h.fs].sum-h.sc.sc);
        }
    }
}
void calc1(){
    dfs(0,0);
    ans[1]=max(ans[1],v[0].sum);
    dfs2(0,0);
}
vector<int> t;
void dfs3(int r,int f){
    vector<int> g;
    for(auto h:v[r].ch){
        if(h.fs!=f){
            dfs3(h.fs,r);
            g.push_back(v[h.fs].sum2+h.sc.fs);
        }
    }
    sort(g.begin(),g.end(),greater<int>());
    if(!g.size()){
        return;
    }
    if(g.size()>1){
        for(int i=1;i<g.size();i++){
            t.push_back(g[i]);
        }
    }
    v[r].sum2=g[0];
}
pair<int,pair<int,int> > dfs4(int r,int f){
    pair<int,pair<int,int> > ret={0,{-1,-1}};
    auto c=v[r].dp,d=v[r].dp2;
    for(auto h:v[r].ch){
        if(h.fs!=f){
            ret=max(ret,dfs4(h.fs,r));
            ret=max(ret,{v[r].dp.fs+v[h.fs].dp2.fs+h.sc.fs,{v[r].dp.sc,v[h.fs].dp2.sc}});
            ret=max(ret,{v[r].dp2.fs+v[h.fs].dp.fs+h.sc.sc,{v[r].dp2.sc,v[h.fs].dp.sc}});
            v[r].dp=max(v[r].dp,{v[h.fs].dp.fs+h.sc.sc,v[h.fs].dp.sc});
            v[r].dp2=max(v[r].dp2,{v[h.fs].dp2.fs+h.sc.fs,v[h.fs].dp2.sc});
        }
    }
    reverse(v[r].ch.begin(),v[r].ch.end());
    v[r].dp=c;
    v[r].dp2=d;
    for(auto h:v[r].ch){
        if(h.fs!=f){
            ret=max(ret,{v[r].dp.fs+v[h.fs].dp2.fs+h.sc.fs,{v[r].dp.sc,v[h.fs].dp2.sc}});
            ret=max(ret,{v[r].dp2.fs+v[h.fs].dp.fs+h.sc.sc,{v[r].dp2.sc,v[h.fs].dp.sc}});
            v[r].dp=max(v[r].dp,{v[h.fs].dp.fs+h.sc.sc,v[h.fs].dp.sc});
            v[r].dp2=max(v[r].dp2,{v[h.fs].dp2.fs+h.sc.fs,v[h.fs].dp2.sc});
        }
    }
    return ret;
}
void calc2(){
    for(int i=0;i<n;i++){
        if(v[i].ch.size()==1){
            v[i].dp.fs=v[i].sum;
            v[i].dp.sc=i;
            v[i].dp2.sc=i;
        }
    }
    auto h=dfs4(0,0);
    for(int i=0;i<n;i++){
        if(i==h.sc.fs || i==h.sc.sc){
            for(int j=0;j<n;j++){
                v[j].sum2=0;
            }
            t.clear();
            dfs3(i,i);
            t.push_back(v[i].sum2);
            sort(t.begin(),t.end(),greater<int>());
            int nw=v[i].sum;
            while(t.size()<=n){
                t.push_back(0);
            }
            for(int j=2;j<=n;j++){
                nw+=t[j-2];
                ans[j]=max(ans[j],nw);
            }
        }
    }
    assert(ans[2]==h.fs);
}
signed main(){
    AquA;
    cin >> n;
    v.resize(n);
    for(int i=1;i<n;i++){
        int a,b;
        cin >> a >> b;
        a--;
        b--;
        int c,d;
        cin >> c >> d;
        zz+=c+d;
        v[a].ch.push_back({b,{c,d}});
        v[b].ch.push_back({a,{d,c}});
    }
    ans.resize(n+1);
    calc1();
    calc2();
    
    int q;
    cin >> q;
    for(int i=0;i<q;i++){
        int a;
        cin >> a;
        cout << zz-ans[a] << "\n";
    }
    return 0;
}

Compilation message (stderr)

designated_cities.cpp: In function 'void dfs3(long long int, long long int)':
designated_cities.cpp:56:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for(int i=1;i<g.size();i++){
      |                     ~^~~~~~~~~
designated_cities.cpp: In function 'void calc2()':
designated_cities.cpp:106:27: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  106 |             while(t.size()<=n){
      |                   ~~~~~~~~^~~

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