oj.uz

Submission #1091269

# Submission time Handle Problem Language Result Execution time Memory
1091269 2024-09-20T10:15:17 Z pokmui9909 Designated Cities (JOI19_designated_cities) C++17
7 / 100
 170 ms 35416 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] = Sum - *max_element(Val + 1, Val + N + 1);
    Dia(1, -1, 0);
    ll V = U;
    Dia(V, -1, 0);
    Ans[2] = Sum - (mxD + Val[V]) / 2;
    
    cin >> Q;
    while(Q--){
        ll t; cin >> t;
        cout << Ans[t] << '\n';
    }
}

Subtask #1
0 / 6.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 116 ms 25808 KB Output is correct
3 Correct 170 ms 35416 KB Output is correct
4 Correct 113 ms 25936 KB Output is correct
5 Correct 104 ms 25800 KB Output is correct
6 Correct 125 ms 27220 KB Output is correct
7 Correct 94 ms 25084 KB Output is correct
8 Correct 146 ms 35152 KB Output is correct
9 Correct 68 ms 23804 KB Output is correct

Subtask #3
0 / 9.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 116 ms 25808 KB Output is correct
3 Correct 170 ms 35416 KB Output is correct
4 Correct 113 ms 25936 KB Output is correct
5 Correct 104 ms 25800 KB Output is correct
6 Correct 125 ms 27220 KB Output is correct
7 Correct 94 ms 25084 KB Output is correct
8 Correct 146 ms 35152 KB Output is correct
9 Correct 68 ms 23804 KB Output is correct
10 Incorrect 2 ms 12632 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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