oj.uz

Submission #1108366

# Submission time Handle Problem Language Result Execution time Memory
1108366 2024-11-04T01:56:41 Z Zero_OP Designated Cities (JOI19_designated_cities) C++14
7 / 100
 226 ms 43320 KB 
#include <bits/stdc++.h>

using namespace std;

#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define sz(v) (int)v.size()

template<typename T>
    bool minimize(T& a, const T& b){
        if(a > b){
            return a = b, true;
        }
        return false;
    }
template<typename T>
    bool maximize(T& a, const T& b){
        if(a < b){
            return a = b, true;
        }
        return false;
    }

using ll = long long;
using ld = long double;
using ull = unsigned long long;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

    int N;
    cin >> N;
    vector<vector<tuple<int, int, int>>> adj(N);
    for(int i = 0; i < N - 1; ++i){
        int u, v, c, d;
        cin >> u >> v >> c >> d;
        --u, --v;
        adj[u].emplace_back(v, c, d);
        adj[v].emplace_back(u, d, c);
    }

    vector<ll> f(N), g(N), up(N), down(N);

    function<void(int, int)> dfs = [&](int u, int p){
        for(auto [v, c, d] : adj[u]) if(v != p){
            down[v] = down[u] + c;
            up[v] = up[u] + d;
            dfs(v, u);
            f[u] += f[v] + c;
        }
    };

    dfs(0, -1);
    g[0] = f[0];

    function<void(int, int)> reroot_dfs = [&](int u, int p){
        for(auto [v, c, d] : adj[u]) if(v != p){
            g[v] = g[u] - c + d;
            reroot_dfs(v, u);
        }
    };

    reroot_dfs(0, -1);
    vector<long long> answer(N + 1, LLONG_MAX);

    for(int i = 0; i < N; ++i){
        minimize(answer[1], g[i]);
    }

    const long long inf = 1e18;
    vector<pair<long long, int>> lowest(N, {-inf, -1});
    tuple<long long, int, int> solution_for_two_leaves = {inf, -1, -1};

    for(int u = 0; u < N; ++u){
        if((int)adj[u].size() == 1){
            lowest[u] = {down[u], u};
        }
    }

    function<void(int, int)> dfs_dp = [&](int u, int p){
        pair<long long, int> A = lowest[u], B = {-inf, -1};

        for(auto [v, c, d] : adj[u]) if(v != p){
            dfs_dp(v, u);

            if(A < lowest[v]){
                B = A;
                A = lowest[v];
            } else maximize(B, lowest[v]);

            maximize(lowest[u], lowest[v]);
        }

        if(B.first != -inf){
            long long delta = 2 * down[u] - A.first - B.first + up[u];
            int u = A.second, v = B.second;

            minimize(solution_for_two_leaves, make_tuple(delta, u, v));
        }
    };

    dfs_dp(0, -1);

    long long delta;
    int l1, l2;
    tie(delta, l1, l2) = solution_for_two_leaves;
    answer[2] = f[0] + delta;

    int Q;
    cin >> Q;
    while(Q--){
        int k;
        cin >> k;
        cout << answer[k] << '\n';
    }

    return 0;
}

Compilation message

designated_cities.cpp: In lambda function:
designated_cities.cpp:51:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   51 |         for(auto [v, c, d] : adj[u]) if(v != p){
      |                  ^
designated_cities.cpp: In lambda function:
designated_cities.cpp:63:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   63 |         for(auto [v, c, d] : adj[u]) if(v != p){
      |                  ^
designated_cities.cpp: In lambda function:
designated_cities.cpp:89:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   89 |         for(auto [v, c, d] : adj[u]) if(v != p){
      |                  ^

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 1 ms 336 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 1 ms 336 KB Output is correct
2 Correct 122 ms 24128 KB Output is correct
3 Correct 165 ms 42568 KB Output is correct
4 Correct 122 ms 24136 KB Output is correct
5 Correct 132 ms 24100 KB Output is correct
6 Correct 190 ms 26932 KB Output is correct
7 Correct 132 ms 24060 KB Output is correct
8 Correct 220 ms 43320 KB Output is correct
9 Correct 98 ms 24548 KB Output is correct

Subtask #3
0 / 9.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 122 ms 24128 KB Output is correct
3 Correct 165 ms 42568 KB Output is correct
4 Correct 122 ms 24136 KB Output is correct
5 Correct 132 ms 24100 KB Output is correct
6 Correct 190 ms 26932 KB Output is correct
7 Correct 132 ms 24060 KB Output is correct
8 Correct 220 ms 43320 KB Output is correct
9 Correct 98 ms 24548 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Incorrect 226 ms 24136 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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