oj.uz

Submission #530123

# Submission time Handle Problem Language Result Execution time Memory
530123 2022-02-24T16:25:19 Z 4fecta Designated Cities (JOI19_designated_cities) C++17
16 / 100
 279 ms 46964 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define ld long double
#define pii pair<int, int>
#define f first
#define s second
#define boost() cin.tie(0), cin.sync_with_stdio(0)

struct edge {
    int u, f, b;
};

const int MN = 200005;

int n, q, u, v, w, x, cost, ans[MN], dp[MN], node[MN];
vector<edge> a[MN];

void dfs1(int cur, int par) {
    for (auto nxt : a[cur]) {
        if (nxt.u == par) continue;
        cost += nxt.f;
        dfs1(nxt.u, cur);
    }
}

void dfs2(int cur, int par) {
    ans[1] = min(ans[1], cost);
    for (auto nxt : a[cur]) {
        if (nxt.u == par) continue;
        cost += nxt.b - nxt.f;
        dfs2(nxt.u, cur);
        cost += nxt.f - nxt.b;
    }
}

void dfs3(int cur, int par) {
    node[cur] = cur;
    for (auto nxt : a[cur]) {
        if (nxt.u == par) continue;
        cost += nxt.b - nxt.f;
        dfs3(nxt.u, cur);
        cost += nxt.f - nxt.b;
        int val = dp[cur] + dp[nxt.u] + nxt.f;
        if (cost - val < ans[2]) {
            ans[2] = cost - val;
            u = node[cur], v = node[nxt.u];
        }
        if (dp[cur] < dp[nxt.u] + nxt.f) {
            dp[cur] = dp[nxt.u] + nxt.f;
            node[cur] = node[nxt.u];
        }
    }
}

void solve1() {
    dfs1(1, 0);
    dfs2(1, 0);
}

void solve_other() {
    dfs3(1, 0);
}

int32_t main() {
    boost();

    memset(ans, 0x3f, sizeof(ans));
    cin >> n;
    for (int i = 1; i < n; i++) {
        cin >> u >> v >> w >> x;
        a[u].push_back({v, w, x});
        a[v].push_back({u, x, w});
    }
    solve1();
    solve_other();
    cin >> q;
    while (q--) {
        cin >> x;
        printf("%lld\n", ans[x]);
    }

    return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6604 KB Output is correct
2 Incorrect 4 ms 6572 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 4 ms 6584 KB Output is correct
2 Correct 243 ms 23260 KB Output is correct
3 Correct 268 ms 38508 KB Output is correct
4 Correct 232 ms 23216 KB Output is correct
5 Correct 230 ms 23048 KB Output is correct
6 Correct 226 ms 25524 KB Output is correct
7 Correct 198 ms 21988 KB Output is correct
8 Correct 274 ms 39128 KB Output is correct
9 Correct 123 ms 19528 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 230 ms 29196 KB Output is correct
3 Correct 279 ms 46964 KB Output is correct
4 Correct 238 ms 27800 KB Output is correct
5 Correct 257 ms 29020 KB Output is correct
6 Correct 231 ms 31916 KB Output is correct
7 Correct 137 ms 27016 KB Output is correct
8 Correct 272 ms 39308 KB Output is correct
9 Correct 122 ms 25180 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6584 KB Output is correct
2 Correct 243 ms 23260 KB Output is correct
3 Correct 268 ms 38508 KB Output is correct
4 Correct 232 ms 23216 KB Output is correct
5 Correct 230 ms 23048 KB Output is correct
6 Correct 226 ms 25524 KB Output is correct
7 Correct 198 ms 21988 KB Output is correct
8 Correct 274 ms 39128 KB Output is correct
9 Correct 123 ms 19528 KB Output is correct
10 Correct 4 ms 6476 KB Output is correct
11 Correct 230 ms 29196 KB Output is correct
12 Correct 279 ms 46964 KB Output is correct
13 Correct 238 ms 27800 KB Output is correct
14 Correct 257 ms 29020 KB Output is correct
15 Correct 231 ms 31916 KB Output is correct
16 Correct 137 ms 27016 KB Output is correct
17 Correct 272 ms 39308 KB Output is correct
18 Correct 122 ms 25180 KB Output is correct
19 Correct 3 ms 6568 KB Output is correct
20 Incorrect 232 ms 29264 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 6604 KB Output is correct
2 Incorrect 4 ms 6572 KB Output isn't correct
3 Halted 0 ms 0 KB -