oj.uz

Submission #384808

# Submission time Handle Problem Language Result Execution time Memory
384808 2021-04-02T10:27:05 Z kostia244 Designated Cities (JOI19_designated_cities) C++17
13 / 100
 300 ms 31852 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 2e5 + 12;
int n, cst[2*maxn];
ll edgesum = 0;
vector<array<int, 2>> g[maxn];


ll sub[maxn];
void sub_cost(int v, int p) {
    sub[v] = 0;
    for(auto [i, id] : g[v]) if(i != p) {
        sub_cost(i, v);
        sub[v] += sub[i] + cst[id];
    }
}
ll arb[maxn];
void reroot_cost(int v, int p, ll sum) {
    arb[v] = sum;
    for(auto [i, id] : g[v]) if(i!=p) {
        reroot_cost(i, v, sum-cst[id]+cst[id^1]);
    }
}
ll greedy[maxn], used[maxn];
array<ll, 2> find_leaf(int v, int p) {
    array<ll, 2> ans = {0, v};
    for(auto [i, id] : g[v]) if(i != p) {
        auto t = find_leaf(i, v);
        //cout << t[0]+( cst[id^1]*!used[id^1]) << endl;
        t[0] += cst[id^1]*!used[id^1];
        ans = max(ans, t);
    }
    return ans;
}


int par[maxn], par_edge[maxn];
void find_pars(int v, int p) {
    for(auto [i, id] : g[v]) if(i != p) {
        par[i] = v;
        par_edge[i] = id^1;
        find_pars(i, v);
    }
}

void solve(int v) {
    for(int i = 0; i < 2*n; i++) used[i] = 0;
    find_pars(v, 0);
    sub_cost(v, 0);
    ll cur = sub[v];
    for(int i = 2; i <= n; i++) {
        auto [add, x] = find_leaf(v, 0);
        cur += add;
        greedy[i] = min(greedy[i], edgesum - cur);
        for(; x != v; x = par[x]) {
            used[par_edge[x]] = 1;
        }
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for(int f, t, x, y, i = 1; i < n; i++) {
        cin >> f >> t >> cst[2*i-1] >> cst[2*i-2];
        edgesum += cst[2*i-1];
        edgesum += cst[2*i-2];
        g[f].push_back({t, 2*i-2});
        g[t].push_back({f, 2*i-1});
    }
    sub_cost(1, 0);
    reroot_cost(1, 0, sub[1]);
    memset(greedy, 0x4f, sizeof greedy);
    if(n <= 16)
    for(int i = 1; i <= n; i++) {
        if(g[i].size() == 1) {
            solve(i);
        }
    }
    int q;
    cin >> q;
    greedy[1] = edgesum-*max_element(arb+1, arb+n+1);
    for(int t; q--;) {
        cin >> t;
        cout << greedy[t] << '\n';
    }
}

Compilation message

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:65:19: warning: unused variable 'x' [-Wunused-variable]
   65 |     for(int f, t, x, y, i = 1; i < n; i++) {
      |                   ^
designated_cities.cpp:65:22: warning: unused variable 'y' [-Wunused-variable]
   65 |     for(int f, t, x, y, i = 1; i < n; i++) {
      |                      ^

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6636 KB Output is correct
2 Correct 5 ms 6636 KB Output is correct
3 Correct 6 ms 6784 KB Output is correct
4 Correct 5 ms 6636 KB Output is correct
5 Correct 5 ms 6636 KB Output is correct
6 Correct 5 ms 6636 KB Output is correct
7 Correct 6 ms 6636 KB Output is correct
8 Correct 5 ms 6636 KB Output is correct
9 Correct 5 ms 6636 KB Output is correct
10 Correct 6 ms 6636 KB Output is correct
11 Correct 5 ms 6636 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6636 KB Output is correct
2 Correct 246 ms 18668 KB Output is correct
3 Correct 288 ms 31340 KB Output is correct
4 Correct 240 ms 19692 KB Output is correct
5 Correct 266 ms 19764 KB Output is correct
6 Correct 300 ms 21528 KB Output is correct
7 Correct 228 ms 19736 KB Output is correct
8 Correct 299 ms 31852 KB Output is correct
9 Correct 151 ms 20192 KB Output is correct

Subtask #3
0 / 9.0

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

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6636 KB Output is correct
2 Correct 5 ms 6636 KB Output is correct
3 Correct 6 ms 6784 KB Output is correct
4 Correct 5 ms 6636 KB Output is correct
5 Correct 5 ms 6636 KB Output is correct
6 Correct 5 ms 6636 KB Output is correct
7 Correct 6 ms 6636 KB Output is correct
8 Correct 5 ms 6636 KB Output is correct
9 Correct 5 ms 6636 KB Output is correct
10 Correct 6 ms 6636 KB Output is correct
11 Correct 5 ms 6636 KB Output is correct
12 Correct 5 ms 6636 KB Output is correct
13 Incorrect 7 ms 6764 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6636 KB Output is correct
2 Correct 246 ms 18668 KB Output is correct
3 Correct 288 ms 31340 KB Output is correct
4 Correct 240 ms 19692 KB Output is correct
5 Correct 266 ms 19764 KB Output is correct
6 Correct 300 ms 21528 KB Output is correct
7 Correct 228 ms 19736 KB Output is correct
8 Correct 299 ms 31852 KB Output is correct
9 Correct 151 ms 20192 KB Output is correct
10 Correct 5 ms 6636 KB Output is correct
11 Incorrect 256 ms 18692 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6636 KB Output is correct
2 Correct 5 ms 6636 KB Output is correct
3 Correct 6 ms 6784 KB Output is correct
4 Correct 5 ms 6636 KB Output is correct
5 Correct 5 ms 6636 KB Output is correct
6 Correct 5 ms 6636 KB Output is correct
7 Correct 6 ms 6636 KB Output is correct
8 Correct 5 ms 6636 KB Output is correct
9 Correct 5 ms 6636 KB Output is correct
10 Correct 6 ms 6636 KB Output is correct
11 Correct 5 ms 6636 KB Output is correct
12 Correct 5 ms 6636 KB Output is correct
13 Correct 246 ms 18668 KB Output is correct
14 Correct 288 ms 31340 KB Output is correct
15 Correct 240 ms 19692 KB Output is correct
16 Correct 266 ms 19764 KB Output is correct
17 Correct 300 ms 21528 KB Output is correct
18 Correct 228 ms 19736 KB Output is correct
19 Correct 299 ms 31852 KB Output is correct
20 Correct 151 ms 20192 KB Output is correct
21 Correct 5 ms 6636 KB Output is correct
22 Incorrect 256 ms 18692 KB Output isn't correct
23 Halted 0 ms 0 KB -