Submission #1163375

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163375		Math4Life2020	Designated Cities (JOI19_designated_cities)	C++20	100 / 100	896 ms	69168 KiB

designated_cities

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;

const ll Nm = 2e5+5;
bool found[Nm];
vector<array<ll,3>> adj[Nm]; //{x, forward edge cost, back edge cost}

vector<pii> q2; //queue for cost 2 vector: {cost, x}
pii dmax[Nm]; //{max distance, x to reach with}
ll sts[Nm]; //subtree size!
ll sumf = 0; //sum of forward edges

inline pii fz(pii p1, pii p2) {
    if (p1.first>p2.first) {
        return p1;
    }
    return p2;
}

void getq2(ll xc, ll prt) {
    dmax[xc]={0,xc};
    for (auto A0: adj[xc]) {
        ll y = A0[0];
        if (y!=prt && !found[y]) {
            getq2(y,xc);
            sumf += A0[2];
            dmax[xc]=fz(dmax[xc],{dmax[y].first+A0[1],dmax[y].second});
            q2.push_back({dmax[y].first+A0[1],dmax[y].second});
        }
    }
}

ll wsts(ll xc, ll prt) {
    sts[xc]=1;
    for (auto A0: adj[xc]) {
        ll y = A0[0];
        if (y!=prt && !found[y]) {
            sts[xc]+=wsts(y,xc);
        }
    }
    return sts[xc];
}

ll getctr(ll xc, ll prt, ll M) {
    for (auto A0: adj[xc]) {
        ll y = A0[0];
        if (y!=prt && !found[y]) {
            if (sts[y]*2>M) {
                return getctr(y,xc,M);
            }
        }
    }
    return xc;
}

//return: {cost 1, cost 2} vectors
pair<vector<ll>,vector<ll>> solve(ll xc, ll prt) { //current x, parent
    //cost 2 vector is easy: just greedy
    q2.clear();
    sumf = 0;
    getq2(xc,prt);
    ll cnump = 0;
    set<ll> xused;
    ll M = q2.size()+1;
    vector<ll> cost2(M+1,0);
    cost2[0]=sumf;
    sort(q2.rbegin(),q2.rend());
    for (pii p0: q2) {
        if (xused.find(p0.second)!=xused.end()) {
            continue;
        }
        cnump++;
        sumf += p0.first;
        cost2[cnump]=sumf;
        xused.insert(p0.second);
    }
    while (cnump<M) {
        cnump++;
        cost2[cnump]=sumf;
    }
    //now do cost 1 vector; this is harder...
    ll M1 = wsts(xc,prt);
    assert(M==M1);
    ll yc = getctr(xc,prt,M);
    //cout << "xc="<<xc<<", prt="<<prt<<" gives yc="<<yc<<"\n";
    found[yc]=1;
    vector<ll> ayc; //adjacent to yc
    vector<vector<ll>> ac1; //adjacent to yc: cost 1
    vector<vector<ll>> ac2; //adjacent to yc: cost 2
    ll cx = 1; ll cv = 0; //current # active, current value 
    ll sc02 = 0; //sum of cost2[0] for all
    vector<ll> cupd; //current update
    for (auto A0: adj[yc]) { //{y, forward, backward}
        ll zc = A0[0];
        if (!found[zc]) {
            auto A1 = solve(zc,yc);
            ayc.push_back(zc);
            ll L = A1.first.size();
            for (ll i=1;i<L;i++) {
                A1.second[i]+=A0[1];
                A1.first[i]+=A0[1];
            }
            for (ll i=0;i<L;i++) {
                A1.second[i]+=A0[2];
            }
            cv += A1.second[0];
            sc02 += A1.second[0];
            for (ll i=1;i<L;i++) {
                cupd.push_back(A1.second[i]-A1.second[i-1]);
            }
            ac1.push_back(A1.first);
            ac2.push_back(A1.second);
        }
    }
    //cout << "sc02="<<sc02<<"\n";
    ll FDEG = ayc.size();
    vector<ll> cost1(M+1,0);
    //process cost1
    sort(cupd.rbegin(),cupd.rend());
    cost1[1]=max(cost1[1],cv);
    for (ll ndv: cupd) {
        cx++;
        cv+=ndv;
        cost1[cx]=max(cost1[cx],cv);
    }
    for (ll T=0;T<FDEG;T++) {
        ll L = ac1[T].size();
        for (ll i=1;i<L;i++) {
            cost1[i]=max(cost1[i],ac1[T][i]-ac2[T][0]+sc02);
        }
    }
    if (FDEG>=2) {
        vector<pii> vupd0; //vector of updates (0->1)
        cx = 0;
        cv = 0;
        for (ll T=0;T<FDEG;T++) {
            cv += ac2[T][0];
            if (ac2[T].size()>=2) {
                vupd0.push_back({ac2[T][1]-ac2[T][0],T});
            }
        }
        sort(vupd0.rbegin(),vupd0.rend());
        if (vupd0.size()>=2) {
            cx = 2;
            cv += vupd0[0].first+vupd0[1].first;
            cost1[cx]=max(cost1[cx],cv);
            vector<ll> vupd1;
            for (ll TC=2;TC<vupd0.size();TC++) {
                vupd1.push_back(vupd0[TC].first);
            }
            for (ll T=0;T<FDEG;T++) {
                ll L = ac1[T].size();
                for (ll i=1;i<(L-1);i++) {
                    vupd1.push_back(ac2[T][i+1]-ac2[T][i]);
                }
            }
            sort(vupd1.rbegin(),vupd1.rend());
            for (ll x0: vupd1) {
                cx++;
                cv+=x0;
                cost1[cx]=max(cost1[cx],cv);
            }
        }
    }
    // cout << "xc,yc,prt="<<xc<<","<<yc<<","<<prt<<"\n";
    // for (ll x0: cost1) {
    //     cout << "cost1: "<<x0<<"\n";
    // }
    // for (ll x0: cost2) {
    //     cout << "cost2: "<<x0<<"\n";
    // }
    return {cost1,cost2};
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
    ll N; cin >> N;
    for (ll i=0;i<N;i++) {
        found[i]=0;
    }
    ll SUMALL = 0;
    for (ll i=0;i<(N-1);i++) {
        ll a,b,c,d; cin >> a >> b >> c >> d;
        a--; b--;
        SUMALL += (c+d);
        adj[a].push_back({b,c,d});
        adj[b].push_back({a,d,c});
    }
    pair<vector<ll>,vector<ll>> FINANS = solve(0,-1);
    ll Q; cin >> Q;
    for (ll q=0;q<Q;q++) {
        ll e1; cin >> e1;
        cout << SUMALL-FINANS.first[e1] << "\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