oj.uz

Submission #511473

# Submission time Handle Problem Language Result Execution time Memory
511473 2022-01-15T23:34:32 Z couplefire Designated Cities (JOI19_designated_cities) C++17
16 / 100
 293 ms 49220 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int N = 200005;

int n, q; ll ans[N];
vector<array<int, 3>> adj[N];

namespace Task1{
    ll sum, cur;

    void dfs1(int v, int p){
        for(auto [u, d1, d2] : adj[v]){
            sum += d2;
            if(u==p) continue;
            cur += d2; 
            dfs1(u, v);
        }
    }

    void dfs2(int v, int p){
        ans[1] = min(ans[1], sum-cur);
        for(auto [u, d1, d2] : adj[v]){
            if(u==p) continue;
            cur -= d2; cur += d1;
            dfs2(u, v);
            cur += d2; cur -= d1;
        }
    }

    void solve(){
        dfs1(0, 0);
        dfs2(0, 0);
    }
}

namespace Task2{
    ll sum, tot, dp[N], best[N];
    int best1, best2;

    void dfs1(int v, int p){
        for(auto [u, d1, d2] : adj[v]){
            sum += d2;
            if(u==p) continue;
            tot += d2;
            dfs1(u, v);
        }
    }

    void dfs2(int v, int p, ll val1, ll val2){
        ll tmp = tot-val1+val2;
        array<ll, 2> mx1 = {0, v}, mx2 = {0, v}; 
        best[v] = v;
        for(auto [u, d1, d2] : adj[v]){
            if(u==p) continue;
            dfs2(u, v, val1+d2, val2+d1);
            if(dp[u]+d1>dp[v])
                dp[v] = dp[u]+d1, best[v] = best[u];
            if(array<ll, 2>{dp[u]+d1, best[u]}>mx1)
                mx2 = mx1, mx1 = {dp[u]+d1, best[u]};
            else if(array<ll, 2>{dp[u]+d1, best[u]}>mx2)
                mx2 = {dp[u]+d1, best[u]};
        }
        if(sum-tmp-mx1[0]-mx2[0]<ans[2])
            best1 = mx1[1], best2 = mx2[1], ans[2] = sum-tmp-mx1[0]-mx2[0];
    }

    void solve(){
        dfs1(0, 0);
        dfs2(0, 0, 0, 0);
    }
}

namespace Task3{
    void solve(){

    }
}

int main(){
    // freopen("a.in", "r", stdin);
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for(int i = 0; i<n-1; ++i){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        --a; --b;
        adj[a].push_back({b, c, d});
        adj[b].push_back({a, d, c});
    }
    memset(ans, 63, sizeof ans);
    Task1::solve();
    Task2::solve();
    Task3::solve();
    cin >> q;
    while(q--){
        int x; cin >> x;
        cout << ans[x] << '\n';
    }
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6560 KB Output is correct
2 Incorrect 4 ms 6560 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 3 ms 6476 KB Output is correct
2 Correct 219 ms 18212 KB Output is correct
3 Correct 293 ms 39248 KB Output is correct
4 Correct 203 ms 18212 KB Output is correct
5 Correct 202 ms 18044 KB Output is correct
6 Correct 236 ms 21344 KB Output is correct
7 Correct 166 ms 18056 KB Output is correct
8 Correct 268 ms 39968 KB Output is correct
9 Correct 118 ms 17032 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6476 KB Output is correct
2 Correct 225 ms 24364 KB Output is correct
3 Correct 291 ms 49220 KB Output is correct
4 Correct 212 ms 22960 KB Output is correct
5 Correct 212 ms 24232 KB Output is correct
6 Correct 232 ms 27960 KB Output is correct
7 Correct 137 ms 24428 KB Output is correct
8 Correct 276 ms 38252 KB Output is correct
9 Correct 118 ms 22856 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6476 KB Output is correct
2 Correct 219 ms 18212 KB Output is correct
3 Correct 293 ms 39248 KB Output is correct
4 Correct 203 ms 18212 KB Output is correct
5 Correct 202 ms 18044 KB Output is correct
6 Correct 236 ms 21344 KB Output is correct
7 Correct 166 ms 18056 KB Output is correct
8 Correct 268 ms 39968 KB Output is correct
9 Correct 118 ms 17032 KB Output is correct
10 Correct 4 ms 6476 KB Output is correct
11 Correct 225 ms 24364 KB Output is correct
12 Correct 291 ms 49220 KB Output is correct
13 Correct 212 ms 22960 KB Output is correct
14 Correct 212 ms 24232 KB Output is correct
15 Correct 232 ms 27960 KB Output is correct
16 Correct 137 ms 24428 KB Output is correct
17 Correct 276 ms 38252 KB Output is correct
18 Correct 118 ms 22856 KB Output is correct
19 Correct 4 ms 6556 KB Output is correct
20 Incorrect 229 ms 24296 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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