oj.uz

Submission #592645

# Submission time Handle Problem Language Result Execution time Memory
592645 2022-07-09T12:00:58 Z Lobo Designated Cities (JOI19_designated_cities) C++17
100 / 100
 1892 ms 64972 KB 
#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

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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 4992 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 3 ms 5028 KB Output is correct
11 Correct 4 ms 5028 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 1185 ms 44640 KB Output is correct
3 Correct 1803 ms 62688 KB Output is correct
4 Correct 1278 ms 49600 KB Output is correct
5 Correct 522 ms 50964 KB Output is correct
6 Correct 1583 ms 52816 KB Output is correct
7 Correct 435 ms 51116 KB Output is correct
8 Correct 1812 ms 63088 KB Output is correct
9 Correct 283 ms 51592 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 1306 ms 44648 KB Output is correct
3 Correct 1892 ms 64788 KB Output is correct
4 Correct 1344 ms 49676 KB Output is correct
5 Correct 521 ms 51000 KB Output is correct
6 Correct 1628 ms 52980 KB Output is correct
7 Correct 309 ms 51236 KB Output is correct
8 Correct 1725 ms 58924 KB Output is correct
9 Correct 296 ms 51196 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 4992 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 3 ms 5028 KB Output is correct
11 Correct 4 ms 5028 KB Output is correct
12 Correct 3 ms 5076 KB Output is correct
13 Correct 6 ms 5460 KB Output is correct
14 Correct 6 ms 5588 KB Output is correct
15 Correct 6 ms 5512 KB Output is correct
16 Correct 7 ms 5556 KB Output is correct
17 Correct 7 ms 5528 KB Output is correct
18 Correct 7 ms 5460 KB Output is correct
19 Correct 6 ms 5460 KB Output is correct
20 Correct 7 ms 5496 KB Output is correct
21 Correct 7 ms 5460 KB Output is correct
22 Correct 7 ms 5556 KB Output is correct
23 Correct 6 ms 5524 KB Output is correct
24 Correct 6 ms 5460 KB Output is correct
25 Correct 7 ms 5656 KB Output is correct
26 Correct 4 ms 5588 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 1185 ms 44640 KB Output is correct
3 Correct 1803 ms 62688 KB Output is correct
4 Correct 1278 ms 49600 KB Output is correct
5 Correct 522 ms 50964 KB Output is correct
6 Correct 1583 ms 52816 KB Output is correct
7 Correct 435 ms 51116 KB Output is correct
8 Correct 1812 ms 63088 KB Output is correct
9 Correct 283 ms 51592 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 1306 ms 44648 KB Output is correct
12 Correct 1892 ms 64788 KB Output is correct
13 Correct 1344 ms 49676 KB Output is correct
14 Correct 521 ms 51000 KB Output is correct
15 Correct 1628 ms 52980 KB Output is correct
16 Correct 309 ms 51236 KB Output is correct
17 Correct 1725 ms 58924 KB Output is correct
18 Correct 296 ms 51196 KB Output is correct
19 Correct 3 ms 5124 KB Output is correct
20 Correct 1194 ms 51008 KB Output is correct
21 Correct 1809 ms 64972 KB Output is correct
22 Correct 1329 ms 49884 KB Output is correct
23 Correct 1294 ms 51104 KB Output is correct
24 Correct 1282 ms 49904 KB Output is correct
25 Correct 1253 ms 51080 KB Output is correct
26 Correct 1231 ms 50024 KB Output is correct
27 Correct 554 ms 50976 KB Output is correct
28 Correct 1573 ms 52684 KB Output is correct
29 Correct 1248 ms 51044 KB Output is correct
30 Correct 1086 ms 50188 KB Output is correct
31 Correct 414 ms 51224 KB Output is correct
32 Correct 1826 ms 59396 KB Output is correct
33 Correct 279 ms 51672 KB Output is correct

Subtask #6
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 4992 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 3 ms 5028 KB Output is correct
11 Correct 4 ms 5028 KB Output is correct
12 Correct 3 ms 5076 KB Output is correct
13 Correct 1185 ms 44640 KB Output is correct
14 Correct 1803 ms 62688 KB Output is correct
15 Correct 1278 ms 49600 KB Output is correct
16 Correct 522 ms 50964 KB Output is correct
17 Correct 1583 ms 52816 KB Output is correct
18 Correct 435 ms 51116 KB Output is correct
19 Correct 1812 ms 63088 KB Output is correct
20 Correct 283 ms 51592 KB Output is correct
21 Correct 3 ms 5076 KB Output is correct
22 Correct 1306 ms 44648 KB Output is correct
23 Correct 1892 ms 64788 KB Output is correct
24 Correct 1344 ms 49676 KB Output is correct
25 Correct 521 ms 51000 KB Output is correct
26 Correct 1628 ms 52980 KB Output is correct
27 Correct 309 ms 51236 KB Output is correct
28 Correct 1725 ms 58924 KB Output is correct
29 Correct 296 ms 51196 KB Output is correct
30 Correct 3 ms 5076 KB Output is correct
31 Correct 6 ms 5460 KB Output is correct
32 Correct 6 ms 5588 KB Output is correct
33 Correct 6 ms 5512 KB Output is correct
34 Correct 7 ms 5556 KB Output is correct
35 Correct 7 ms 5528 KB Output is correct
36 Correct 7 ms 5460 KB Output is correct
37 Correct 6 ms 5460 KB Output is correct
38 Correct 7 ms 5496 KB Output is correct
39 Correct 7 ms 5460 KB Output is correct
40 Correct 7 ms 5556 KB Output is correct
41 Correct 6 ms 5524 KB Output is correct
42 Correct 6 ms 5460 KB Output is correct
43 Correct 7 ms 5656 KB Output is correct
44 Correct 4 ms 5588 KB Output is correct
45 Correct 3 ms 5124 KB Output is correct
46 Correct 1194 ms 51008 KB Output is correct
47 Correct 1809 ms 64972 KB Output is correct
48 Correct 1329 ms 49884 KB Output is correct
49 Correct 1294 ms 51104 KB Output is correct
50 Correct 1282 ms 49904 KB Output is correct
51 Correct 1253 ms 51080 KB Output is correct
52 Correct 1231 ms 50024 KB Output is correct
53 Correct 554 ms 50976 KB Output is correct
54 Correct 1573 ms 52684 KB Output is correct
55 Correct 1248 ms 51044 KB Output is correct
56 Correct 1086 ms 50188 KB Output is correct
57 Correct 414 ms 51224 KB Output is correct
58 Correct 1826 ms 59396 KB Output is correct
59 Correct 279 ms 51672 KB Output is correct
60 Correct 4 ms 5036 KB Output is correct
61 Correct 1344 ms 53668 KB Output is correct
62 Correct 1888 ms 64468 KB Output is correct
63 Correct 1274 ms 52348 KB Output is correct
64 Correct 1147 ms 53620 KB Output is correct
65 Correct 1224 ms 52400 KB Output is correct
66 Correct 1300 ms 53712 KB Output is correct
67 Correct 1311 ms 52312 KB Output is correct
68 Correct 607 ms 53648 KB Output is correct
69 Correct 1635 ms 55144 KB Output is correct
70 Correct 1296 ms 53572 KB Output is correct
71 Correct 1135 ms 52940 KB Output is correct
72 Correct 468 ms 54524 KB Output is correct
73 Correct 1803 ms 60476 KB Output is correct
74 Correct 311 ms 55860 KB Output is correct