oj.uz

Submission #653833

# Submission time Handle Problem Language Result Execution time Memory
653833 2022-10-28T12:12:11 Z dooompy Designated Cities (JOI19_designated_cities) C++17
7 / 100
 1078 ms 34248 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 7;

struct Edge {
    int v, a, b;

    Edge() {}

    Edge(int v_, int a_, int b_) : v(v_), a(a_), b(b_) {}
};

int n;
vector<Edge> e[N];
bool used[N];
int sz[N];
long long ans[N];

void dfs(int u, int p = -1) {
    sz[u] = 1;
    for (auto [v, a, b] : e[u]) {
        if (!used[v] && v != p) {
            dfs(v, u);
            sz[u] += sz[v];
        }
    }
}

int centroid(int u, int all, int p = -1) {
    for (auto [v, a, b] : e[u]) {
        if (!used[v] && v != p && 2 * sz[v] > all) {
            return centroid(v, all, u);
        }
    }
    return u;
}

long long zhfs(int u, int p = -1) {
    long long res = 0;
    for (auto [v, a, b] : e[u]) {
        if (!used[v] && v != p) {
            res += zhfs(v, u);
            res += b;
        }
    }
    return res;
}

long long go(int u, int t, vector<pair<long long, int>> &d, int p = -1) {
    vector<long long> cur;
    for (auto [v, a, b] : e[u]) {
        if (!used[v] && v != p) {
            cur.push_back(go(v, t, d, u) + a);
        }
    }
    if (cur.empty()) return 0;
    swap(cur[0], cur[max_element(begin(cur), end(cur)) - begin(cur)]);
    for (int i = 1; i < (int)cur.size(); ++i) {
        d.emplace_back(cur[i], t);
    }
    return cur[0];
}

void solve(int u, long long bonus) {
    dfs(u);
    vector<pair<long long, int>> ch;
    ch.reserve(e[u].size());
    for (auto [v, a, b] : e[u]) {
        if (!used[v]) {
            long long z = zhfs(v, u);
            bonus += b;
            bonus += z;
            ch.emplace_back(a - z - b, v);
        }
    }
    ans[1] = max(ans[1], bonus);
    used[u] = true;
    {
        vector<pair<long long, int>> d;
        d.reserve(sz[u]);
        for (auto [v, a, b] : e[u]) {
            if (!used[v]) d.emplace_back(go(v, v, d) + a, v);
        }
        sort(rbegin(d), rend(d));
        int f = -1;
        for (int i = 1; i < (int)d.size(); ++i) {
            if (d[i].second != d[0].second) {
                f = i;
                break;
            }
        }
        long long cur = 0;
        for (int i = 0; i < (int)d.size(); ++i) {
            cur += d[i].first;
            ans[i + 2] = max(ans[i + 2], cur + bonus);
//            if (f != -1) ans[i + 1 + (i < f)] = max(ans[i + 1 + (i < f)], cur + (i < f ? d[f].first : 0) + bonus);
        }
    }
    for (auto [delta, v] : ch) {
        bonus += delta;
        solve(centroid(v, sz[v]), bonus);
        bonus -= delta;
    }
}

int main() {
    scanf("%d", &n);
    long long sum = 0;
    for (int i = 0; i < n - 1; ++i) {
        int a, b, c, d;
        scanf("%d%d%d%d", &a, &b, &c, &d);
        --a, --b;
        e[a].emplace_back(b, c, d);
        e[b].emplace_back(a, d, c);
        sum += c;
        sum += d;
    }
    dfs(0);
    solve(centroid(0, n), 0);
    for (int i = 1; i <= n; ++i) {
        ans[i] = sum - ans[i];
    }
    for (int i = 2; i <= n; ++i) {
        ans[i] = min(ans[i], ans[i - 1]);
    }
    int q;
    scanf("%d", &q);
    while (q--) {
        int x;
        scanf("%d", &x);
        cout << ans[x] << "\n";
    }
    return 0;
}

Compilation message

designated_cities.cpp: In function 'void solve(int, long long int)':
designated_cities.cpp:87:13: warning: variable 'f' set but not used [-Wunused-but-set-variable]
   87 |         int f = -1;
      |             ^
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:109:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
designated_cities.cpp:113:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |         scanf("%d%d%d%d", &a, &b, &c, &d);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:129:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
designated_cities.cpp:132:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |         scanf("%d", &x);
      |         ~~~~~^~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 3 ms 5008 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 4948 KB Output is correct
2 Correct 735 ms 22872 KB Output is correct
3 Correct 1006 ms 34248 KB Output is correct
4 Correct 657 ms 21452 KB Output is correct
5 Correct 340 ms 22992 KB Output is correct
6 Correct 859 ms 24568 KB Output is correct
7 Correct 277 ms 24832 KB Output is correct
8 Correct 1078 ms 33936 KB Output is correct
9 Correct 170 ms 28628 KB Output is correct

Subtask #3
0 / 9.0

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

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 3 ms 5008 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 4948 KB Output is correct
2 Correct 735 ms 22872 KB Output is correct
3 Correct 1006 ms 34248 KB Output is correct
4 Correct 657 ms 21452 KB Output is correct
5 Correct 340 ms 22992 KB Output is correct
6 Correct 859 ms 24568 KB Output is correct
7 Correct 277 ms 24832 KB Output is correct
8 Correct 1078 ms 33936 KB Output is correct
9 Correct 170 ms 28628 KB Output is correct
10 Correct 3 ms 5004 KB Output is correct
11 Incorrect 681 ms 22964 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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