Submission #592285

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
592285	2022-07-08T21:12:52 Z	Lobo	Designated Cities (JOI19_designated_cities)	C++17	9 / 100	1679 ms	61660 KB

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];
pair<int,int> dp[maxn];
vector<pair<pair<int,int>,pair<int,int>>> edg;
vector<int> vert, g[maxn], vertcent;

int dfsdeep(int u, int ant, int val) {
    vert.pb(u);
    pai[u] = ant;
    dp[u] = mp(val,u);
    int up = 0;
    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];
        up+= edg[id].sc.fr+edg[id].sc.sc-w;
        up+= dfsdeep(v,u,w);
        dp[u] = max(dp[u],mp(dp[v].fr+val,dp[v].sc));
    }
    return up;
}

void sol(int rt) {
    vert.clear();
    int up = 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));
    }
    sort(all(deeps),greater<pair<int,int>>());

    int qtdc = 1;
    int ans1 = up;
    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 << v << " " << X.fr << endl;

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

    //obriga a escolher de subs diferentes
    ans1 = up;
    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 << 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 << 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 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)));
    }

    findcent(1);
    // for(int i = 1; i <= 1; 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

designated_cities.cpp: In function 'void findcent(long long int)':
designated_cities.cpp:133:9: warning: 'ct' may be used uninitialized in this function [-Wmaybe-uninitialized]
  133 |     int ct;
      |         ^~

Subtask #1
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4948 KB	Output is correct
2	Incorrect	3 ms	4948 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4948 KB	Output is correct
2	Incorrect	1087 ms	41484 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	4948 KB	Output is correct
2	Correct	1174 ms	41476 KB	Output is correct
3	Correct	1679 ms	61660 KB	Output is correct
4	Correct	1205 ms	46512 KB	Output is correct
5	Correct	432 ms	47952 KB	Output is correct
6	Correct	1373 ms	49928 KB	Output is correct
7	Correct	261 ms	48224 KB	Output is correct
8	Correct	1606 ms	55692 KB	Output is correct
9	Correct	244 ms	48044 KB	Output is correct