oj.uz

Submission #825299

# Submission time Handle Problem Language Result Execution time Memory
825299 2023-08-14T17:02:35 Z vjudge1 Designated Cities (JOI19_designated_cities) C++17
16 / 100
 263 ms 41888 KB 
#include <bits/stdc++.h>
using namespace std;

// 123

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

        int n;
        cin >> n;
        vector<vector<tuple<int, int, int>>> adj(n);
        vector<int> deg(n, 0);
        for (int i = 0; i < n - 1; i++) {
                int u, v, a, b;
                cin >> u >> v >> a >> b;
                u--, v--;
                deg[u]++, deg[v]++;
                adj[u].emplace_back(v, a, b);
                adj[v].emplace_back(u, b, a);
        }
        vector<int64_t> f(n, 0);
        function<void(int, int)> dfs1 = [&](int u, int p) {
                for (auto [v, a, b] : adj[u]) {  // a(u->v), b(v->u)
                        if (v == p) continue;
                        dfs1(v, u);
                        f[u] += a + f[v];
                }
        };
        vector<int64_t> g(n, 0);
        function<void(int, int)> dfs2 = [&](int u, int p) {
                for (auto [v, a, b] : adj[u]) {  // a(u->v), b(v->u)
                        if (v == p) continue;
                        g[v] = g[u] - a + b;
                        dfs2(v, u);
                }
        };
        dfs1(0, -1);
        g[0] = f[0];
        dfs2(0, -1);
        int root = min_element(g.begin(), g.end()) - g.begin();
        vector<int64_t> h(n, 0);
        function<void(int, int)> dfs3 = [&](int u, int p) {
                for (auto [v, a, b] : adj[u]) {
                        if (v == p) continue;
                        h[v] = h[u] + a;
                        dfs3(v, u);
                }
        };
        dfs3(root, -1);
        int root2 = max_element(h.begin(), h.end()) - h.begin();
        h[root2] = 0;
        dfs3(root2, -1);
        int64_t best = *max_element(h.begin(), h.end());

        int q;
        cin >> q;

        while (q--) {
                int e;
                cin >> e;
                if (e == 1) {
                        cout << g[root] << '\n';
                } else {
                        cout << g[root2] - best << '\n';
                }
        }
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 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 0 ms 212 KB Output is correct
2 Correct 190 ms 21008 KB Output is correct
3 Correct 263 ms 41880 KB Output is correct
4 Correct 171 ms 23652 KB Output is correct
5 Correct 157 ms 25000 KB Output is correct
6 Correct 177 ms 27364 KB Output is correct
7 Correct 143 ms 24880 KB Output is correct
8 Correct 262 ms 41112 KB Output is correct
9 Correct 100 ms 25588 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 191 ms 18856 KB Output is correct
3 Correct 243 ms 41888 KB Output is correct
4 Correct 159 ms 23844 KB Output is correct
5 Correct 185 ms 25240 KB Output is correct
6 Correct 190 ms 28048 KB Output is correct
7 Correct 111 ms 25176 KB Output is correct
8 Correct 227 ms 36300 KB Output is correct
9 Correct 111 ms 25212 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 190 ms 21008 KB Output is correct
3 Correct 263 ms 41880 KB Output is correct
4 Correct 171 ms 23652 KB Output is correct
5 Correct 157 ms 25000 KB Output is correct
6 Correct 177 ms 27364 KB Output is correct
7 Correct 143 ms 24880 KB Output is correct
8 Correct 262 ms 41112 KB Output is correct
9 Correct 100 ms 25588 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 191 ms 18856 KB Output is correct
12 Correct 243 ms 41888 KB Output is correct
13 Correct 159 ms 23844 KB Output is correct
14 Correct 185 ms 25240 KB Output is correct
15 Correct 190 ms 28048 KB Output is correct
16 Correct 111 ms 25176 KB Output is correct
17 Correct 227 ms 36300 KB Output is correct
18 Correct 111 ms 25212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Incorrect 184 ms 25156 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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