Submission #592645

#	Time	Username	Problem	Language	Result	Execution time	Memory
592645		Lobo	Designated Cities (JOI19_designated_cities)	C++17	100 / 100	1892 ms	64972 KiB

designated_cities

#include<bits/stdc++.h>
using namespace std;

const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

const int maxn = 2e5+10;

int n, q, comp[maxn], mark[maxn], ans[maxn], pai[maxn], blk[maxn], sz[maxn], dw[maxn], up[maxn];
pair<int,int> dp[maxn];
vector<pair<pair<int,int>,pair<int,int>>> edg;
vector<int> vert, g[maxn], vertcent;

void dfsdeep(int u, int ant, int val) {
    vert.pb(u);
    pai[u] = ant;
    dp[u] = mp(val,u);
    for(auto id : g[u]) {
        int v = u^edg[id].fr.fr^edg[id].fr.sc;
        if(v == ant || blk[v]) continue;
        int w;
        if(edg[id].fr.fr == u) w = edg[id].sc.fr;
        else w = edg[id].sc.sc;
        if(ant == 0) 
            comp[v] = v;
        else
            comp[v] = comp[u];
        dfsdeep(v,u,w);
        dp[u] = max(dp[u],mp(dp[v].fr+val,dp[v].sc));
    }
}

void sol(int rt) {
    vert.clear();
    dfsdeep(rt,0,0);
    vector<pair<int,int>> deeps;
    //pego eu mesmo e os melhores dos outros
    for(auto v : vert) {
        mark[v] = 0;
        deeps.pb(mp(dp[v].fr,v));
        // cout << rt << " -" << dp[v].fr << " " << v  << endl;
    }
    sort(all(deeps),greater<pair<int,int>>());

    int qtdc = 1;
    int ans1 = dw[rt]+up[rt];
    ans[1] = max(ans[1],ans1);
    for(auto X : deeps) {
        int v = X.sc;
        if(mark[v]) continue;
        ans1+= dp[v].fr;
        qtdc++;
        ans[qtdc] = max(ans[qtdc],ans1);
        v = dp[v].sc;
        // cout << rt << " -- " << v << " " << X.fr << endl;

        while(v != 0 && mark[v] == 0) {
            mark[v] = 1;
            v = pai[v];
        }
    }

    //obriga a escolher de subs diferentes
    ans1 = dw[rt]+up[rt];
    qtdc = 1;
    for(auto v : vert) {
        mark[v] = 0;
    }
    int v1 = dp[rt].sc;
    ans1+= dp[rt].fr;
    int comp1 = comp[v1];
    while(v1 != 0 && mark[v1] == 0) {
        mark[v1] = 1;
        v1 = pai[v1];
    }
    for(auto X : deeps) {
        int v = X.sc;
        if(mark[v] || comp[dp[v].sc] == comp1) continue;
        ans1+= dp[v].fr;
        qtdc++;
        ans[qtdc] = max(ans[qtdc],ans1);
        v = dp[v].sc;
        // cout << rt << " " << v << " " << X.fr << " " << qtdc << endl;

        while(v != 0 && mark[v] == 0) {
            mark[v] = 1;
            v = pai[v];
        }
        break;
    }

    for(auto X : deeps) {
        int v = X.sc;
        if(mark[v]) continue;
        ans1+= dp[v].fr;
        qtdc++;
        ans[qtdc] = max(ans[qtdc],ans1);
        v = dp[v].sc;
        // cout << rt << " -- " << v << " " << X.fr << endl;

        while(v != 0 && mark[v] == 0) {
            mark[v] = 1;
            v = pai[v];
        }
    }
}

void dfscent(int u, int ant) {
    vertcent.pb(u);
    sz[u] = 1;
    for(auto id : g[u]) {
        int v = edg[id].fr.fr^edg[id].fr.sc^u;
        if(blk[v] || v == ant) continue;
        dfscent(v,u);
        sz[u]+=sz[v];
    }
}

void findcent(int rt) {
    vertcent.clear();
    dfscent(rt,0);
    int ct;
    for(auto u : vertcent) {
        bool ok = true;

        if(sz[rt]-sz[u] > sz[rt]/2) ok = false;
        for(auto id : g[u]) {
            int v = edg[id].fr.fr^edg[id].fr.sc^u;
            if(blk[v] || sz[v] > sz[u]) continue;
            if(sz[v] > sz[rt]/2) ok = false;
        }
        if(ok) ct = u;
    }
    sol(ct);
    blk[ct] = 1;
    for(auto id : g[ct]) {
        int v = edg[id].fr.fr^edg[id].fr.sc^ct;
        if(blk[v]) continue;
        findcent(v);
    }
}

void dfsdw(int u, int ant) {
    dw[u] = 0;
    for(auto id : g[u]) {
        int v = u^edg[id].fr.fr^edg[id].fr.sc;
        if(v == ant) continue;
        int wdw,wup;
        if(u == edg[id].fr.fr) {
            wdw = edg[id].sc.fr;
            wup = edg[id].sc.sc;
        }
        else {
            wdw = edg[id].sc.sc;
            wup = edg[id].sc.fr;
        }
        dfsdw(v,u);
        dw[u]+=dw[v]+wup;
    }
}

void dfsup(int u, int ant) {
    for(auto id : g[u]) {
        int v = u^edg[id].fr.fr^edg[id].fr.sc;
        if(v == ant) continue;
        int wdw,wup;
        if(u == edg[id].fr.fr) {
            wdw = edg[id].sc.fr;
            wup = edg[id].sc.sc;
        }
        else {
            wdw = edg[id].sc.sc;
            wup = edg[id].sc.fr;
        }
        up[v] = up[u]+dw[u]-dw[v]-wup+wdw;
        dfsup(v,u);
    }
}

void solve() {
    cin >> n;
    for(int i = 0; i < n-1; i++) {
        int u,v,w1,w2;
        cin >> u >> v >> w1 >> w2;
        g[u].pb(i);
        g[v].pb(i);
        ans[0]+= w1+w2;
        edg.pb(mp(mp(u,v),mp(w1,w2)));
    }
    dfsdw(1,0);
    dfsup(1,0);

    // for(int i = 1; i <= n; i++) {
    //     cout << i << " " << dw[i] << " " << up[i] << endl;
    // }

    findcent(1);
    // for(int i = 1; i <= n; i++) sol(i);
    for(int i = 2; i <= n; i++) {
        ans[i] = max(ans[i],ans[i-1]);
    }

    cin >> q;
    while(q--) {
        int x; cin >> x;
        cout << ans[0]-ans[x] << endl;
    }
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int tt = 1;
    // cin >> tt;
    while(tt--) {
        solve();
    }

}

Compilation message (stderr)

designated_cities.cpp: In function 'void dfsdw(long long int, long long int)':
designated_cities.cpp:156:13: warning: variable 'wdw' set but not used [-Wunused-but-set-variable]
  156 |         int wdw,wup;
      |             ^~~
designated_cities.cpp: In function 'void findcent(long long int)':
designated_cities.cpp:130:9: warning: 'ct' may be used uninitialized in this function [-Wmaybe-uninitialized]
  130 |     int ct;
      |         ^~

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