oj.uz

Submission #723412

# Submission time Handle Problem Language Result Execution time Memory
723412 2023-04-13T18:37:01 Z doowey Designated Cities (JOI19_designated_cities) C++17
100 / 100
 376 ms 60544 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)2e5 + 10;

struct E{
    int nx;
    int C;
    int D;
};

vector<E> T[N];

ll sol[N];

ll cum;
ll W[N];
pii mx[N];

void dfs0(int u, int pa){
    mx[u] = mp(0ll, u);
    for(auto x : T[u]){
        if(x.nx == pa) continue;
        cum += x.D;
        W[x.nx] = W[u] + x.C - x.D;
        dfs0(x.nx, u);
        mx[u] = max(mx[u], mp(mx[x.nx].fi + x.C, mx[x.nx].se));
    }
}

ll take = 0ll;

ll maxi = 0ll;
int ud;
int vd;

void dfs1(int u, int pa){
    pii r1, r2;
    r1 = r2 = mp(0ll, u);
    pii G;
    for(auto x : T[u]){
        if(x.nx == pa) continue;
        dfs1(x.nx, u);
        G = mx[x.nx];
        G.fi += x.C;
        if(G > r1){
            r2 = r1;
            r1 = G;
        }
        else if(G > r2){
            r2 = G;
        }
    }
    if(cum + W[u] + r1.fi + r2.fi > maxi){
        maxi = cum + W[u] + r1.fi + r2.fi;
        ud = r1.se;
        vd = r2.se;
    }
}

vector<ll> wei[N];

void dfs2(int node, int par){
    wei[node].push_back(0ll);
    for(auto x : T[node]){
        if(x.nx == par) continue;
        dfs2(x.nx, node);
        wei[x.nx].back() += x.C;
        cum += x.D;
        if(wei[node].size() < wei[x.nx].size()) swap(wei[node], wei[x.nx]);
        if(wei[node].back() > wei[x.nx].back()) swap(wei[node].back(), wei[x.nx].back());
        for(auto y : wei[x.nx]) {
            wei[node].push_back(y);
        }
        wei[x.nx].clear();
    }
}

int main(){
    fastIO;
    //freopen("in.txt", "r", stdin);
    int n;
    cin >> n;
    int ui, vi, ci, di;
    for(int i = 1; i < n; i ++ ){
        cin >> ui >> vi >> ci >> di;
        T[ui].push_back({vi, ci, di});
        T[vi].push_back({ui, di, ci});
        take += ci + di;
    }
    cum = 0ll;
    dfs0(1, -1);
    for(int i = 1; i <= n; i ++ ){
        sol[1] = max(sol[1], W[i] + cum);
    }
    dfs1(1, -1);
    cum = 0ll;
    dfs2(ud, -1);
    sort(wei[ud].begin(), wei[ud].end());
    reverse(wei[ud].begin(), wei[ud].end());
    for(int ln = 0; ln < n - 1; ln ++ ){
        cum += wei[ud][ln];
        sol[ln + 2] = max(sol[ln + 2], cum);
    }
    int q;
    cin >> q;
    int r;
    for(int ii = 1; ii <= q; ii ++ ){
        cin >> r;
        cout << take - sol[r] << "\n";
    }
    return 0;
}

Subtask #1
6.0 / 6.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 287 ms 38716 KB Output is correct
3 Correct 339 ms 52088 KB Output is correct
4 Correct 280 ms 43892 KB Output is correct
5 Correct 290 ms 40280 KB Output is correct
6 Correct 313 ms 43488 KB Output is correct
7 Correct 254 ms 38820 KB Output is correct
8 Correct 341 ms 57544 KB Output is correct
9 Correct 178 ms 38900 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9812 KB Output is correct
2 Correct 295 ms 38664 KB Output is correct
3 Correct 327 ms 60288 KB Output is correct
4 Correct 274 ms 43452 KB Output is correct
5 Correct 295 ms 40592 KB Output is correct
6 Correct 300 ms 43688 KB Output is correct
7 Correct 206 ms 38568 KB Output is correct
8 Correct 325 ms 51664 KB Output is correct
9 Correct 202 ms 38524 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9720 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 5 ms 9684 KB Output is correct
12 Correct 5 ms 9684 KB Output is correct
13 Correct 6 ms 10036 KB Output is correct
14 Correct 7 ms 10068 KB Output is correct
15 Correct 6 ms 9940 KB Output is correct
16 Correct 7 ms 9940 KB Output is correct
17 Correct 7 ms 9940 KB Output is correct
18 Correct 6 ms 9940 KB Output is correct
19 Correct 6 ms 9940 KB Output is correct
20 Correct 7 ms 9940 KB Output is correct
21 Correct 7 ms 10016 KB Output is correct
22 Correct 7 ms 9940 KB Output is correct
23 Correct 7 ms 9940 KB Output is correct
24 Correct 7 ms 9940 KB Output is correct
25 Correct 7 ms 10068 KB Output is correct
26 Correct 6 ms 9940 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 287 ms 38716 KB Output is correct
3 Correct 339 ms 52088 KB Output is correct
4 Correct 280 ms 43892 KB Output is correct
5 Correct 290 ms 40280 KB Output is correct
6 Correct 313 ms 43488 KB Output is correct
7 Correct 254 ms 38820 KB Output is correct
8 Correct 341 ms 57544 KB Output is correct
9 Correct 178 ms 38900 KB Output is correct
10 Correct 5 ms 9812 KB Output is correct
11 Correct 295 ms 38664 KB Output is correct
12 Correct 327 ms 60288 KB Output is correct
13 Correct 274 ms 43452 KB Output is correct
14 Correct 295 ms 40592 KB Output is correct
15 Correct 300 ms 43688 KB Output is correct
16 Correct 206 ms 38568 KB Output is correct
17 Correct 325 ms 51664 KB Output is correct
18 Correct 202 ms 38524 KB Output is correct
19 Correct 6 ms 9728 KB Output is correct
20 Correct 299 ms 45164 KB Output is correct
21 Correct 332 ms 60544 KB Output is correct
22 Correct 279 ms 43924 KB Output is correct
23 Correct 316 ms 45000 KB Output is correct
24 Correct 303 ms 44464 KB Output is correct
25 Correct 299 ms 45620 KB Output is correct
26 Correct 301 ms 43996 KB Output is correct
27 Correct 290 ms 40448 KB Output is correct
28 Correct 311 ms 43388 KB Output is correct
29 Correct 330 ms 44604 KB Output is correct
30 Correct 304 ms 43384 KB Output is correct
31 Correct 231 ms 38680 KB Output is correct
32 Correct 321 ms 52468 KB Output is correct
33 Correct 204 ms 38836 KB Output is correct

Subtask #6
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9720 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 5 ms 9684 KB Output is correct
12 Correct 5 ms 9684 KB Output is correct
13 Correct 287 ms 38716 KB Output is correct
14 Correct 339 ms 52088 KB Output is correct
15 Correct 280 ms 43892 KB Output is correct
16 Correct 290 ms 40280 KB Output is correct
17 Correct 313 ms 43488 KB Output is correct
18 Correct 254 ms 38820 KB Output is correct
19 Correct 341 ms 57544 KB Output is correct
20 Correct 178 ms 38900 KB Output is correct
21 Correct 5 ms 9812 KB Output is correct
22 Correct 295 ms 38664 KB Output is correct
23 Correct 327 ms 60288 KB Output is correct
24 Correct 274 ms 43452 KB Output is correct
25 Correct 295 ms 40592 KB Output is correct
26 Correct 300 ms 43688 KB Output is correct
27 Correct 206 ms 38568 KB Output is correct
28 Correct 325 ms 51664 KB Output is correct
29 Correct 202 ms 38524 KB Output is correct
30 Correct 5 ms 9684 KB Output is correct
31 Correct 6 ms 10036 KB Output is correct
32 Correct 7 ms 10068 KB Output is correct
33 Correct 6 ms 9940 KB Output is correct
34 Correct 7 ms 9940 KB Output is correct
35 Correct 7 ms 9940 KB Output is correct
36 Correct 6 ms 9940 KB Output is correct
37 Correct 6 ms 9940 KB Output is correct
38 Correct 7 ms 9940 KB Output is correct
39 Correct 7 ms 10016 KB Output is correct
40 Correct 7 ms 9940 KB Output is correct
41 Correct 7 ms 9940 KB Output is correct
42 Correct 7 ms 9940 KB Output is correct
43 Correct 7 ms 10068 KB Output is correct
44 Correct 6 ms 9940 KB Output is correct
45 Correct 6 ms 9728 KB Output is correct
46 Correct 299 ms 45164 KB Output is correct
47 Correct 332 ms 60544 KB Output is correct
48 Correct 279 ms 43924 KB Output is correct
49 Correct 316 ms 45000 KB Output is correct
50 Correct 303 ms 44464 KB Output is correct
51 Correct 299 ms 45620 KB Output is correct
52 Correct 301 ms 43996 KB Output is correct
53 Correct 290 ms 40448 KB Output is correct
54 Correct 311 ms 43388 KB Output is correct
55 Correct 330 ms 44604 KB Output is correct
56 Correct 304 ms 43384 KB Output is correct
57 Correct 231 ms 38680 KB Output is correct
58 Correct 321 ms 52468 KB Output is correct
59 Correct 204 ms 38836 KB Output is correct
60 Correct 6 ms 9728 KB Output is correct
61 Correct 327 ms 48348 KB Output is correct
62 Correct 369 ms 60088 KB Output is correct
63 Correct 336 ms 46940 KB Output is correct
64 Correct 344 ms 48316 KB Output is correct
65 Correct 309 ms 46752 KB Output is correct
66 Correct 346 ms 47804 KB Output is correct
67 Correct 335 ms 46992 KB Output is correct
68 Correct 327 ms 43600 KB Output is correct
69 Correct 340 ms 46056 KB Output is correct
70 Correct 336 ms 46868 KB Output is correct
71 Correct 323 ms 46036 KB Output is correct
72 Correct 297 ms 42112 KB Output is correct
73 Correct 376 ms 54552 KB Output is correct
74 Correct 220 ms 42992 KB Output is correct