oj.uz

Submission #384817

# Submission time Handle Problem Language Result Execution time Memory
384817 2021-04-02T11:00:37 Z kostia244 Designated Cities (JOI19_designated_cities) C++17
16 / 100
 387 ms 43500 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]+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, -(1ll<<60));
    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;
    //cout << arb[3] << " " << arb[4] << endl;
    //cout << sol[0] << "/ " << edgesum << 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]);
    //for(int i = 1; i <= n; i++) cout << arb[i] << " "; cout << endl;
    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:99:19: warning: unused variable 'x' [-Wunused-variable]
   99 |     for(int f, t, x, y, i = 1; i < n; i++) {
      |                   ^
designated_cities.cpp:99:22: warning: unused variable 'y' [-Wunused-variable]
   99 |     for(int f, t, x, y, i = 1; i < n; i++) {
      |                      ^
designated_cities.cpp:109:10: warning: unused variable 'point' [-Wunused-variable]
  109 |     auto point = solve2();
      |          ^~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6636 KB Output is correct
2 Incorrect 5 ms 6636 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 5 ms 6636 KB Output is correct
2 Correct 353 ms 24812 KB Output is correct
3 Correct 387 ms 35948 KB Output is correct
4 Correct 352 ms 24428 KB Output is correct
5 Correct 322 ms 24292 KB Output is correct
6 Correct 356 ms 25836 KB Output is correct
7 Correct 277 ms 24288 KB Output is correct
8 Correct 387 ms 36204 KB Output is correct
9 Correct 189 ms 24672 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6636 KB Output is correct
2 Correct 348 ms 23660 KB Output is correct
3 Correct 371 ms 43500 KB Output is correct
4 Correct 354 ms 28524 KB Output is correct
5 Correct 312 ms 29668 KB Output is correct
6 Correct 376 ms 31852 KB Output is correct
7 Correct 198 ms 30044 KB Output is correct
8 Correct 378 ms 37500 KB Output is correct
9 Correct 201 ms 30056 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6636 KB Output is correct
2 Incorrect 5 ms 6636 KB Output isn't correct
3 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 353 ms 24812 KB Output is correct
3 Correct 387 ms 35948 KB Output is correct
4 Correct 352 ms 24428 KB Output is correct
5 Correct 322 ms 24292 KB Output is correct
6 Correct 356 ms 25836 KB Output is correct
7 Correct 277 ms 24288 KB Output is correct
8 Correct 387 ms 36204 KB Output is correct
9 Correct 189 ms 24672 KB Output is correct
10 Correct 5 ms 6636 KB Output is correct
11 Correct 348 ms 23660 KB Output is correct
12 Correct 371 ms 43500 KB Output is correct
13 Correct 354 ms 28524 KB Output is correct
14 Correct 312 ms 29668 KB Output is correct
15 Correct 376 ms 31852 KB Output is correct
16 Correct 198 ms 30044 KB Output is correct
17 Correct 378 ms 37500 KB Output is correct
18 Correct 201 ms 30056 KB Output is correct
19 Correct 5 ms 6636 KB Output is correct
20 Incorrect 339 ms 29676 KB Output isn't correct
21 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 Incorrect 5 ms 6636 KB Output isn't correct
3 Halted 0 ms 0 KB -