oj.uz

Submission #1091272

# Submission time Handle Problem Language Result Execution time Memory
1091272 2024-09-20T10:22:37 Z pokmui9909 Designated Cities (JOI19_designated_cities) C++17
16 / 100
 157 ms 41804 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define x first
#define y second

struct Edge{
    ll v, a, b;
};
vector<Edge> T[200005], C[200005];
ll N, Q, Sum = 0, Ans[200005], Val[200005];

void cal1(ll u, ll p){
    for(auto e : T[u]){
        if(e.v == p) continue;
        Val[1] += e.b;
        cal1(e.v, u);
    }
}
void cal2(ll u, ll p){
    for(auto e : T[u]){
        if(e.v == p) continue;
        Val[e.v] = Val[u] - e.b + e.a;
        cal2(e.v, u);
    }
}
ll mxD = 0, U = 1;
void Dia(ll u, ll p, ll d){
    if(mxD < d + Val[u]){
        mxD = d + Val[u], U = u;
    }
    for(auto e : T[u]){
        if(e.v == p) continue;
        Dia(e.v, u, d + e.a + e.b);
    }
}

int main(){
    cin.tie(0) -> sync_with_stdio(0);

    cin >> N;
    for(ll i = 1; i < N; i++){
        ll u, v, a, b; cin >> u >> v >> a >> b;
        T[u].push_back({v, a, b}); T[v].push_back({u, b, a});
        Sum += a + b;
    }
    cal1(1, -1); cal2(1, -1);
    Ans[1] = *max_element(Val + 1, Val + N + 1);
    Dia(1, -1, 0);
    ll V = U;
    mxD = 0; Dia(V, -1, 0);
    Ans[2] = (mxD + Val[V]) / 2;

    cin >> Q;
    while(Q--){
        ll t; cin >> t;
        cout << Sum - Ans[t] << '\n';
    }
}

Subtask #1
0 / 6.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 122 ms 25260 KB Output is correct
3 Correct 131 ms 35408 KB Output is correct
4 Correct 93 ms 25936 KB Output is correct
5 Correct 95 ms 25088 KB Output is correct
6 Correct 111 ms 27220 KB Output is correct
7 Correct 84 ms 24168 KB Output is correct
8 Correct 157 ms 34384 KB Output is correct
9 Correct 65 ms 23804 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 118 ms 25168 KB Output is correct
3 Correct 135 ms 41804 KB Output is correct
4 Correct 95 ms 30800 KB Output is correct
5 Correct 120 ms 32144 KB Output is correct
6 Correct 117 ms 33948 KB Output is correct
7 Correct 73 ms 31008 KB Output is correct
8 Correct 126 ms 38768 KB Output is correct
9 Correct 71 ms 29908 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 122 ms 25260 KB Output is correct
3 Correct 131 ms 35408 KB Output is correct
4 Correct 93 ms 25936 KB Output is correct
5 Correct 95 ms 25088 KB Output is correct
6 Correct 111 ms 27220 KB Output is correct
7 Correct 84 ms 24168 KB Output is correct
8 Correct 157 ms 34384 KB Output is correct
9 Correct 65 ms 23804 KB Output is correct
10 Correct 2 ms 12632 KB Output is correct
11 Correct 118 ms 25168 KB Output is correct
12 Correct 135 ms 41804 KB Output is correct
13 Correct 95 ms 30800 KB Output is correct
14 Correct 120 ms 32144 KB Output is correct
15 Correct 117 ms 33948 KB Output is correct
16 Correct 73 ms 31008 KB Output is correct
17 Correct 126 ms 38768 KB Output is correct
18 Correct 71 ms 29908 KB Output is correct
19 Correct 3 ms 12636 KB Output is correct
20 Incorrect 110 ms 31760 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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