oj.uz

Submission #956302

# Submission time Handle Problem Language Result Execution time Memory
956302 2024-04-01T14:27:29 Z Pring Designated Cities (JOI19_designated_cities) C++17
16 / 100
 281 ms 50324 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;

const int MXN = 200005;
int n, q, br, eu[MXN], ev[MXN], a[MXN], b[MXN];
vector<int> eid[MXN];
int ans[MXN];

int nsz[MXN], fsz[MXN], rt;
pii dp[MXN];

void GUIDE(int id, int par) {
    nsz[id] = 0;
    for (auto &e : eid[id]) {
        int i = eu[e] ^ ev[e] ^ id;
        if (i == par) continue;
        if (id == ev[e]) {
            swap(eu[e], ev[e]);
            swap(a[e], b[e]);
        }
        GUIDE(i, id);
        nsz[id] += a[e] + nsz[i];
    }
}

void PUSH(pii &p, int x) {
    if (x >= p.fs) {
        p.sc = p.fs;
        p.fs = x;
    } else p.sc = max(p.sc, x);
}

void DP(int id, int par, int acc) {
    fsz[id] = acc;
    dp[id] = mp(0LL, 0LL);
    for (auto &e : eid[id]) {
        if (eu[e] != id) continue;
        int i = ev[e];
        DP(i, id, acc - a[e] + b[e]);
        PUSH(dp[id], dp[i].fs + a[e]);
    }
}

int CALC_1() {
    return *min_element(fsz + 1, fsz + n + 1);
}

int CALC_2() {
    rt = 1;
    FOR(i, 2, n + 1) if (fsz[rt] - dp[rt].fs - dp[rt].sc > fsz[i] - dp[i].fs - dp[i].sc) rt = i;
    return fsz[rt] - dp[rt].fs - dp[rt].sc;
}

namespace TREE {

    pii son[MXN];
    int acc[MXN];
    multiset<int> MS;
    void get_info(int id, int par) {
        son[id] = mp(0LL, 0LL);
        for (auto &e : eid[id]) {
            if (eu[e] != id) continue;
            int i = ev[e];
            get_info(i, id);
            son[id] = max(son[id], mp(a[e] + son[i].fs, e));
        }
    }

    void decompose(int id, int par, int val) {
        debug(id, par, val);
        if (eid[id].size() == 1) {
            MS.insert(val);
            return;
        }
        decompose(ev[son[id].sc], id, val + a[son[id].sc]);
        for (auto &e : eid[id]) {
            if (eu[e] != id) continue;
            if (e == son[id].sc) continue;
            decompose(ev[e], id, a[e]);
        }
    }

    void DO(int rt) {
        get_info(rt, 0);
        for (auto &e : eid[rt]) {
            decompose(ev[e], rt, a[e]);
        }
        MS.erase(MS.find(dp[rt].fs));
        MS.erase(MS.find(dp[rt].sc));
        int ptr = 3;
        for (auto it = MS.rbegin(); it != MS.rend(); it++, ptr++) ans[ptr] = ans[ptr - 1] - *it;
        assert(false);
        FOR(i, ptr, n + 1) ans[i] = ans[i - 1];
    }
}

void miku() {
    cin >> n;
    FOR(i, 0, n - 1) {
        cin >> eu[i] >> ev[i] >> a[i] >> b[i];
        eid[eu[i]].push_back(i);
        eid[ev[i]].push_back(i);
    }
    GUIDE(1, 0);
    DP(1, 0, nsz[1]);
    ans[1] = CALC_1();
    ans[2] = CALC_2();
    // GUIDE(rt, 0);
    // TREE::DO(rt);
    cin >> q;
    while (q--) {
        cin >> br;
        cout << ans[br] << '\n';
    }
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    miku();
    return 0;
}

Compilation message

designated_cities.cpp: In function 'void TREE::decompose(long long int, long long int, long long int)':
designated_cities.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
designated_cities.cpp:87:9: note: in expansion of macro 'debug'
   87 |         debug(id, par, val);
      |         ^~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18776 KB Output is correct
2 Incorrect 3 ms 19036 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 18780 KB Output is correct
2 Correct 190 ms 33496 KB Output is correct
3 Correct 237 ms 47440 KB Output is correct
4 Correct 179 ms 31868 KB Output is correct
5 Correct 195 ms 33356 KB Output is correct
6 Correct 212 ms 35456 KB Output is correct
7 Correct 150 ms 33448 KB Output is correct
8 Correct 281 ms 48304 KB Output is correct
9 Correct 130 ms 33860 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19032 KB Output is correct
2 Correct 227 ms 33336 KB Output is correct
3 Correct 267 ms 50324 KB Output is correct
4 Correct 173 ms 31912 KB Output is correct
5 Correct 206 ms 33620 KB Output is correct
6 Correct 223 ms 35752 KB Output is correct
7 Correct 110 ms 33540 KB Output is correct
8 Correct 263 ms 42584 KB Output is correct
9 Correct 134 ms 33560 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18776 KB Output is correct
2 Incorrect 3 ms 19036 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 18780 KB Output is correct
2 Correct 190 ms 33496 KB Output is correct
3 Correct 237 ms 47440 KB Output is correct
4 Correct 179 ms 31868 KB Output is correct
5 Correct 195 ms 33356 KB Output is correct
6 Correct 212 ms 35456 KB Output is correct
7 Correct 150 ms 33448 KB Output is correct
8 Correct 281 ms 48304 KB Output is correct
9 Correct 130 ms 33860 KB Output is correct
10 Correct 3 ms 19032 KB Output is correct
11 Correct 227 ms 33336 KB Output is correct
12 Correct 267 ms 50324 KB Output is correct
13 Correct 173 ms 31912 KB Output is correct
14 Correct 206 ms 33620 KB Output is correct
15 Correct 223 ms 35752 KB Output is correct
16 Correct 110 ms 33540 KB Output is correct
17 Correct 263 ms 42584 KB Output is correct
18 Correct 134 ms 33560 KB Output is correct
19 Correct 3 ms 18780 KB Output is correct
20 Incorrect 221 ms 33224 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 18776 KB Output is correct
2 Incorrect 3 ms 19036 KB Output isn't correct
3 Halted 0 ms 0 KB -