oj.uz

Submission #384813

# Submission time Handle Problem Language Result Execution time Memory
384813 2021-04-02T10:46:38 Z kostia244 Designated Cities (JOI19_designated_cities) C++17
7 / 100
 406 ms 35692 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;
}

array<ll, 2> far[maxn];
void sub_far(int v, int p) {
    far[v] = {0, -(1ll<<56)};
    for(auto &[i, id] : g[v]) if(i != p) {
        sub_far(i, v);
        auto t = far[i];
        t[0] += cst[id^1];
        t[1] += cst[id^1];
        if(far[v][0] < t[0])
            swap(far[v][0], t[0]);
        far[v][1] = max(far[v][1], t[0]);
    }
}
ll F[maxn];
void reroot_far(int v, int p, ll over) {
    F[v] = max(far[v][0], over);
    //cout << v << " -- " << F[v] << endl;
    for(auto [i, id] : g[v]) if(i != p) {
        reroot_far(i, v, cst[id^1]+max(over, far[i][0]+cst[id^1] == far[v][0] ? far[v][1] : far[v][0]));
    }
}
ll solFor2 = 0;
int solve2() {
    sub_far(1, 0);
    reroot_far(1, 0, 0);
    array<ll, 2> sol = {-(1ll<<60), -1};
    for(int i = 1; i <= n; i++)
        sol = max(sol, {F[i]+arb[i], i});
    //cout << edgesum << " ? " << sol[0] << " " << sol[1] << endl;
    solFor2 = edgesum - sol[0];
    return sol[1];
}

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]);
    auto point = solve2();

    memset(greedy, 0x4f, sizeof greedy);
    if(n <= 2000)
        solve(point);

    int q;
    cin >> q;
    greedy[1] = edgesum-*max_element(arb+1, arb+n+1);
    greedy[2] = solFor2;
    for(int t; q--;) {
        cin >> t;
        cout << greedy[t] << '\n';
    }
}

Compilation message

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

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 6784 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6636 KB Output is correct
2 Correct 329 ms 23388 KB Output is correct
3 Correct 406 ms 35052 KB Output is correct
4 Correct 331 ms 23404 KB Output is correct
5 Correct 336 ms 23524 KB Output is correct
6 Correct 332 ms 25188 KB Output is correct
7 Correct 303 ms 23400 KB Output is correct
8 Correct 388 ms 35692 KB Output is correct
9 Correct 187 ms 23772 KB Output is correct

Subtask #3
0 / 9.0

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

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 6784 KB Output isn't correct
2 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 329 ms 23388 KB Output is correct
3 Correct 406 ms 35052 KB Output is correct
4 Correct 331 ms 23404 KB Output is correct
5 Correct 336 ms 23524 KB Output is correct
6 Correct 332 ms 25188 KB Output is correct
7 Correct 303 ms 23400 KB Output is correct
8 Correct 388 ms 35692 KB Output is correct
9 Correct 187 ms 23772 KB Output is correct
10 Incorrect 5 ms 6636 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 6784 KB Output isn't correct
2 Halted 0 ms 0 KB -