oj.uz

Submission #723411

# Submission time Handle Problem Language Result Execution time Memory
723411 2023-04-13T18:36:06 Z doowey Designated Cities (JOI19_designated_cities) C++14
23 / 100
 2000 ms 55948 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]);
        for(auto y : wei[x.nx]) {
            wei[node].push_back(y);
        }
        wei[x.nx].clear();
    }
    sort(wei[node].begin(), wei[node].end());
}

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 7 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9728 KB Output is correct
5 Correct 5 ms 9724 KB Output is correct
6 Correct 7 ms 9684 KB Output is correct
7 Correct 7 ms 9636 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 9724 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 1767 ms 45532 KB Output is correct
3 Execution timed out 2064 ms 55948 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Execution timed out 2079 ms 43636 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9728 KB Output is correct
5 Correct 5 ms 9724 KB Output is correct
6 Correct 7 ms 9684 KB Output is correct
7 Correct 7 ms 9636 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 9724 KB Output is correct
12 Correct 5 ms 9684 KB Output is correct
13 Correct 11 ms 10068 KB Output is correct
14 Correct 19 ms 10208 KB Output is correct
15 Correct 9 ms 9996 KB Output is correct
16 Correct 9 ms 10068 KB Output is correct
17 Correct 9 ms 10000 KB Output is correct
18 Correct 8 ms 10068 KB Output is correct
19 Correct 7 ms 10068 KB Output is correct
20 Correct 8 ms 10068 KB Output is correct
21 Correct 15 ms 10088 KB Output is correct
22 Correct 9 ms 10004 KB Output is correct
23 Correct 7 ms 10016 KB Output is correct
24 Correct 9 ms 9968 KB Output is correct
25 Correct 27 ms 10216 KB Output is correct
26 Correct 7 ms 9996 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 1767 ms 45532 KB Output is correct
3 Execution timed out 2064 ms 55948 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9728 KB Output is correct
5 Correct 5 ms 9724 KB Output is correct
6 Correct 7 ms 9684 KB Output is correct
7 Correct 7 ms 9636 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 9724 KB Output is correct
12 Correct 6 ms 9684 KB Output is correct
13 Correct 1767 ms 45532 KB Output is correct
14 Execution timed out 2064 ms 55948 KB Time limit exceeded
15 Halted 0 ms 0 KB -