oj.uz

Submission #1108383

# Submission time Handle Problem Language Result Execution time Memory
1108383 2024-11-04T03:18:01 Z Zero_OP Designated Cities (JOI19_designated_cities) C++14
100 / 100
 428 ms 75548 KB 
#include <bits/stdc++.h>

using namespace std;

#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define sz(v) (int)v.size()

template<typename T>
    bool minimize(T& a, const T& b){
        if(a > b){
            return a = b, true;
        }
        return false;
    }
template<typename T>
    bool maximize(T& a, const T& b){
        if(a < b){
            return a = b, true;
        }
        return false;
    }

using ll = long long;
using ld = long double;
using ull = unsigned long long;

const ll inf = 1e18;

struct SegmentTree{
    vector<ll> lazy;
    vector<pair<ll, int>> st;

    SegmentTree(int n) : lazy(n << 2, 0), st(n << 2, make_pair(0, 0)) {}

    void build(int id, int l, int r){
        if(l == r){
            st[id] = {0, l};
        } else{
            int mid = l + r >> 1;
            build(id << 1, l, mid);
            build(id << 1 | 1, mid + 1, r);
            st[id] = max(st[id << 1], st[id << 1 | 1]);
        }
    }

    void apply(int id, long long val){
        st[id].first += val;
        lazy[id] += val;
    }

    void lazyDown(int id){
        apply(id << 1, lazy[id]);
        apply(id << 1 | 1, lazy[id]);
        lazy[id] = 0;
    }

    void update(int id, int l, int r, int u, int v, long long val){
        if(u <= l && r <= v) apply(id, val);
        else{
            int mid = l + r >> 1;
            lazyDown(id);
            if(u <= mid) update(id << 1, l, mid, u, v, val);
            if(mid < v) update(id << 1 | 1, mid + 1, r, u, v, val);
            st[id] = max(st[id << 1], st[id << 1 | 1]);
        }
    }

    pair<ll, int> query(){
        return st[1];
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

    int N;
    cin >> N;
    vector<vector<tuple<int, int, int>>> adj(N);
    for(int i = 0; i < N - 1; ++i){
        int u, v, c, d;
        cin >> u >> v >> c >> d;
        --u, --v;
        adj[u].emplace_back(v, c, d);
        adj[v].emplace_back(u, d, c);
    }

    vector<ll> f(N), g(N), up(N), down(N);

    function<void(int, int)> dfs = [&](int u, int p){
        for(auto [v, c, d] : adj[u]) if(v != p){
            down[v] = down[u] + c;
            up[v] = up[u] + d;
            dfs(v, u);
            f[u] += f[v] + c;
        }
    };

    dfs(0, -1);
    g[0] = f[0];

    function<void(int, int)> reroot_dfs = [&](int u, int p){
        for(auto [v, c, d] : adj[u]) if(v != p){
            g[v] = g[u] - c + d;
            reroot_dfs(v, u);
        }
    };

    reroot_dfs(0, -1);
    vector<long long> answer(N + 1, LLONG_MAX);

    for(int i = 0; i < N; ++i){
        minimize(answer[1], g[i]);
    }

    vector<pair<long long, int>> lowest(N, {-inf, -1});
    tuple<long long, int, int> solution_for_two_leaves = {inf, -1, -1};

    for(int u = 0; u < N; ++u){
        if((int)adj[u].size() == 1){
            lowest[u] = {down[u], u};
        }
    }

    function<void(int, int)> dfs_dp = [&](int u, int p){
        pair<long long, int> A = lowest[u], B = {-inf, -1};

        for(auto [v, c, d] : adj[u]) if(v != p){
            dfs_dp(v, u);

            if(A < lowest[v]){
                B = A;
                A = lowest[v];
            } else maximize(B, lowest[v]);

            maximize(lowest[u], lowest[v]);
        }

        if(B.first != -inf){
            long long delta = 2 * down[u] - A.first - B.first + up[u] - down[u];
            int u = A.second, v = B.second;

            minimize(solution_for_two_leaves, make_tuple(delta, u, v));
        }
    };

    dfs_dp(0, -1);

    long long delta;
    int l1, l2;
    tie(delta, l1, l2) = solution_for_two_leaves;
    answer[2] = f[0] + delta;

    vector<int> parent(N), down_e(N), tin(N), tout(N), tour(N);
    int timer_dfs = 0;

    function<void(int, int)> re_dfs = [&](int u, int p){
        tour[tin[u] = timer_dfs++] = u;
        for(auto [v, c, d] : adj[u]) if(v != p){
            parent[v] = u;
            down_e[v] = c;
            re_dfs(v, u);
        }
        tout[u] = timer_dfs - 1;
    };

    re_dfs(l1, -1);
    SegmentTree T(N);
    T.build(1, 0, N - 1);

    for(int i = 0; i < N; ++i) if(i != l1){
        T.update(1, 0, N - 1, tin[i], tout[i], down_e[i]);
    }

    vector<bool> used(N, false);
    used[l1] = true;

    auto pave = [&](int u) -> void{
        while(!used[u]){
            used[u] = true;
            T.update(1, 0, N - 1, tin[u], tout[u], -down_e[u]);
            T.update(1, 0, N - 1, tin[u], tin[u], -inf);
            u = parent[u];
        }
    };

    pave(l2);

    bool process = true;
    for(int i = 3; i <= N; ++i){
        answer[i] = answer[i - 1];
        if(process){
            pair<ll, int> cur = T.query();

            if(cur.first > 0){
                answer[i] -= cur.first;
                int u = tour[cur.second];
                pave(u);
            } else{
                process = false;
            }
        }
    }

    int Q;
    cin >> Q;
    while(Q--){
        int k;
        cin >> k;
        cout << answer[k] << '\n';
    }

    return 0;
}

Compilation message

designated_cities.cpp: In member function 'void SegmentTree::build(int, int, int)':
designated_cities.cpp:40:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |             int mid = l + r >> 1;
      |                       ~~^~~
designated_cities.cpp: In member function 'void SegmentTree::update(int, int, int, int, int, long long int)':
designated_cities.cpp:61:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |             int mid = l + r >> 1;
      |                       ~~^~~
designated_cities.cpp: In lambda function:
designated_cities.cpp:97:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   97 |         for(auto [v, c, d] : adj[u]) if(v != p){
      |                  ^
designated_cities.cpp: In lambda function:
designated_cities.cpp:109:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  109 |         for(auto [v, c, d] : adj[u]) if(v != p){
      |                  ^
designated_cities.cpp: In lambda function:
designated_cities.cpp:134:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  134 |         for(auto [v, c, d] : adj[u]) if(v != p){
      |                  ^
designated_cities.cpp: In lambda function:
designated_cities.cpp:165:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  165 |         for(auto [v, c, d] : adj[u]) if(v != p){
      |                  ^

Subtask #1
6.0 / 6.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 292 ms 47068 KB Output is correct
3 Correct 292 ms 65352 KB Output is correct
4 Correct 297 ms 47016 KB Output is correct
5 Correct 336 ms 46856 KB Output is correct
6 Correct 365 ms 49736 KB Output is correct
7 Correct 275 ms 46788 KB Output is correct
8 Correct 428 ms 66100 KB Output is correct
9 Correct 251 ms 47356 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 317 ms 47244 KB Output is correct
3 Correct 289 ms 68832 KB Output is correct
4 Correct 271 ms 46904 KB Output is correct
5 Correct 342 ms 46848 KB Output is correct
6 Correct 345 ms 50248 KB Output is correct
7 Correct 262 ms 47092 KB Output is correct
8 Correct 346 ms 59464 KB Output is correct
9 Correct 238 ms 47348 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 592 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 3 ms 848 KB Output is correct
14 Correct 3 ms 1104 KB Output is correct
15 Correct 4 ms 848 KB Output is correct
16 Correct 4 ms 1104 KB Output is correct
17 Correct 3 ms 1020 KB Output is correct
18 Correct 3 ms 848 KB Output is correct
19 Correct 4 ms 848 KB Output is correct
20 Correct 3 ms 848 KB Output is correct
21 Correct 3 ms 848 KB Output is correct
22 Correct 3 ms 1016 KB Output is correct
23 Correct 3 ms 848 KB Output is correct
24 Correct 4 ms 1016 KB Output is correct
25 Correct 5 ms 1272 KB Output is correct
26 Correct 3 ms 848 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 292 ms 47068 KB Output is correct
3 Correct 292 ms 65352 KB Output is correct
4 Correct 297 ms 47016 KB Output is correct
5 Correct 336 ms 46856 KB Output is correct
6 Correct 365 ms 49736 KB Output is correct
7 Correct 275 ms 46788 KB Output is correct
8 Correct 428 ms 66100 KB Output is correct
9 Correct 251 ms 47356 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 317 ms 47244 KB Output is correct
12 Correct 289 ms 68832 KB Output is correct
13 Correct 271 ms 46904 KB Output is correct
14 Correct 342 ms 46848 KB Output is correct
15 Correct 345 ms 50248 KB Output is correct
16 Correct 262 ms 47092 KB Output is correct
17 Correct 346 ms 59464 KB Output is correct
18 Correct 238 ms 47348 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 395 ms 46928 KB Output is correct
21 Correct 386 ms 75548 KB Output is correct
22 Correct 367 ms 52040 KB Output is correct
23 Correct 317 ms 53320 KB Output is correct
24 Correct 324 ms 52304 KB Output is correct
25 Correct 331 ms 53576 KB Output is correct
26 Correct 337 ms 52260 KB Output is correct
27 Correct 327 ms 53136 KB Output is correct
28 Correct 393 ms 56136 KB Output is correct
29 Correct 410 ms 53356 KB Output is correct
30 Correct 356 ms 52436 KB Output is correct
31 Correct 304 ms 53244 KB Output is correct
32 Correct 373 ms 66516 KB Output is correct
33 Correct 267 ms 53748 KB Output is correct

Subtask #6
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 592 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 292 ms 47068 KB Output is correct
14 Correct 292 ms 65352 KB Output is correct
15 Correct 297 ms 47016 KB Output is correct
16 Correct 336 ms 46856 KB Output is correct
17 Correct 365 ms 49736 KB Output is correct
18 Correct 275 ms 46788 KB Output is correct
19 Correct 428 ms 66100 KB Output is correct
20 Correct 251 ms 47356 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 317 ms 47244 KB Output is correct
23 Correct 289 ms 68832 KB Output is correct
24 Correct 271 ms 46904 KB Output is correct
25 Correct 342 ms 46848 KB Output is correct
26 Correct 345 ms 50248 KB Output is correct
27 Correct 262 ms 47092 KB Output is correct
28 Correct 346 ms 59464 KB Output is correct
29 Correct 238 ms 47348 KB Output is correct
30 Correct 1 ms 336 KB Output is correct
31 Correct 3 ms 848 KB Output is correct
32 Correct 3 ms 1104 KB Output is correct
33 Correct 4 ms 848 KB Output is correct
34 Correct 4 ms 1104 KB Output is correct
35 Correct 3 ms 1020 KB Output is correct
36 Correct 3 ms 848 KB Output is correct
37 Correct 4 ms 848 KB Output is correct
38 Correct 3 ms 848 KB Output is correct
39 Correct 3 ms 848 KB Output is correct
40 Correct 3 ms 1016 KB Output is correct
41 Correct 3 ms 848 KB Output is correct
42 Correct 4 ms 1016 KB Output is correct
43 Correct 5 ms 1272 KB Output is correct
44 Correct 3 ms 848 KB Output is correct
45 Correct 1 ms 336 KB Output is correct
46 Correct 395 ms 46928 KB Output is correct
47 Correct 386 ms 75548 KB Output is correct
48 Correct 367 ms 52040 KB Output is correct
49 Correct 317 ms 53320 KB Output is correct
50 Correct 324 ms 52304 KB Output is correct
51 Correct 331 ms 53576 KB Output is correct
52 Correct 337 ms 52260 KB Output is correct
53 Correct 327 ms 53136 KB Output is correct
54 Correct 393 ms 56136 KB Output is correct
55 Correct 410 ms 53356 KB Output is correct
56 Correct 356 ms 52436 KB Output is correct
57 Correct 304 ms 53244 KB Output is correct
58 Correct 373 ms 66516 KB Output is correct
59 Correct 267 ms 53748 KB Output is correct
60 Correct 1 ms 336 KB Output is correct
61 Correct 342 ms 56156 KB Output is correct
62 Correct 407 ms 73676 KB Output is correct
63 Correct 337 ms 54700 KB Output is correct
64 Correct 312 ms 56136 KB Output is correct
65 Correct 301 ms 54760 KB Output is correct
66 Correct 320 ms 56188 KB Output is correct
67 Correct 293 ms 54788 KB Output is correct
68 Correct 296 ms 56080 KB Output is correct
69 Correct 353 ms 58440 KB Output is correct
70 Correct 374 ms 55884 KB Output is correct
71 Correct 318 ms 55384 KB Output is correct
72 Correct 311 ms 56464 KB Output is correct
73 Correct 418 ms 67220 KB Output is correct
74 Correct 290 ms 58100 KB Output is correct