oj.uz

Submission #770542

# Submission time Handle Problem Language Result Execution time Memory
770542 2023-07-01T12:54:32 Z vjudge1 Paths (RMI21_paths) C++17
48 / 100
 600 ms 35104 KB 
#include <bits/stdc++.h>

        using namespace std;
        using ll = long long;

        #define int ll

        int N, K, P[100005], rem[100005];
        int par[100005][20];
        ll ST[400005], lazy[400005];
        ll D[100005];
        int X[100005], Y[100005], C[100005];
        int timer, tin[100005], out[100005], id[100005];
        ll sol[100005];
        vector<int> adj[100005];

        void update(int v, int l, int r, int p, ll val) {
            if(l == r) {
                ST[v] = val;
                lazy[v] = 0;
                return;
            }
            int md = (l + r) / 2;
            if(p <= md) update(v * 2, l, (l + r) / 2, p, val);
            else update(v * 2 + 1, (l + r) / 2 + 1, r, p, val);
            ST[v] = max(ST[v * 2], ST[v * 2 + 1]);
            lazy[v] = 0;
        }
        void prop(int v, int l, int r) {
            if(l == r || lazy[v] == 0) return;
            lazy[v * 2] += lazy[v];
            lazy[v * 2 + 1] += lazy[v];
            ST[v * 2] -= lazy[v];
            ST[v * 2 + 1] -= lazy[v];
            lazy[v] = 0;
        }
        void update(int v, int l, int r, int lo, int hi, ll val) {
            prop(v, l, r);
            if(l > hi || r < lo) return;
            if(l >= lo && r <= hi) {
                ST[v] -= val; lazy[v] += val;
                prop(v, l, r); return;
            }
            update(v * 2, l, (l + r) / 2, lo, hi, val);
            update(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi, val);
            ST[v] = max(ST[v * 2], ST[v * 2 + 1]);
        }
        int query(int v, int l, int r) {
            prop(v, l, r);
            if(l == r) return l;
            if(ST[v * 2] >= ST[v * 2 + 1])
                return query(v * 2, l, (l + r) / 2);
            return query(v * 2 + 1, (l + r) / 2 + 1, r);
        }
        void dfs(int v, int p, ll dep = 0) {
            par[v][0] = p; id[timer] = v;
            tin[v] = timer++; update(1, 0, N - 1, tin[v], dep);
            for(auto u : adj[v]) {
                int nxt = ((X[u] ^ Y[u]) ^ v);
                if(nxt == p) continue;
                P[nxt] = u; dfs(nxt, v, dep + C[u]);
            }
            out[v] = timer - 1;
        }
        void solve(int v, int p) {
            sol[v] = ST[1];
            for(auto u : adj[v]) {
                int nxt = ((X[u] ^ Y[u]) ^ v);
                if(nxt == p) continue;
                update(1, 0, N - 1, 0, N - 1, -C[u]);
                update(1, 0, N - 1, tin[nxt], out[nxt], 2 * C[u]);
                solve(nxt, v);
                update(1, 0, N - 1, 0, N - 1, C[u]);
                update(1, 0, N - 1, tin[nxt], out[nxt], -2 * C[u]);
            }
        }

        int32_t main() {
            ios_base::sync_with_stdio(0);
            cin.tie(0); cout.tie(0);
            cin >> N >> K;
            for(int l = 0; l < N - 1; l++) {
                cin >> X[l] >> Y[l] >> C[l];
                int U = X[l], V = Y[l];
                adj[U].push_back(l);
                adj[V].push_back(l);
            }
            if(K == 1) {
                dfs(1, 1);
                solve(1, 1);
                for(int l = 1; l <= N; l++)
                    cout << sol[l] << "\n";
                return 0;
            }
            for(int l = 1; l <= N; l++) {
                ///memset(ST, 0, sizeof ST);
                ///memset(lazy, 0, sizeof lazy);
                for(int i = 1; i <= N; i++)
                    rem[i] = 0;
                rem[l] = 1;
                ll res = 0; timer = 0; dfs(l, l);
                for(int i = 1; i < 20; i++)
                    for(int j = 1; j <= N; j++)
                        par[j][i] = par[par[j][i - 1]][i - 1];
                for(int i = 0; i < K; i++) {
                    int A = query(1, 0, N - 1); res += ST[1]; A = id[A];
                    ///cout << ST[1] << " ";
                    int B = A;
                    for(int j = 19; j >= 0; j--) {
                        if(rem[par[B][j]] == 0)
                            B = par[B][j];
                    }
                    B = par[B][0];

                    while(A != B) {
                        update(1, 0, N - 1, tin[A], out[A], C[P[A]]);
                        rem[A] = 1; A = par[A][0];
                    }
                }
                cout << res << "\n";
            }
        }

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 8 ms 2900 KB Output is correct
4 Correct 9 ms 2772 KB Output is correct
5 Correct 6 ms 2772 KB Output is correct
6 Correct 9 ms 2816 KB Output is correct
7 Correct 8 ms 2772 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 8 ms 2900 KB Output is correct
4 Correct 9 ms 2772 KB Output is correct
5 Correct 6 ms 2772 KB Output is correct
6 Correct 9 ms 2816 KB Output is correct
7 Correct 8 ms 2772 KB Output is correct
8 Correct 193 ms 3028 KB Output is correct
9 Correct 251 ms 3056 KB Output is correct
10 Correct 248 ms 3028 KB Output is correct
11 Correct 154 ms 3036 KB Output is correct
12 Correct 206 ms 3040 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 8 ms 2900 KB Output is correct
4 Correct 9 ms 2772 KB Output is correct
5 Correct 6 ms 2772 KB Output is correct
6 Correct 9 ms 2816 KB Output is correct
7 Correct 8 ms 2772 KB Output is correct
8 Correct 193 ms 3028 KB Output is correct
9 Correct 251 ms 3056 KB Output is correct
10 Correct 248 ms 3028 KB Output is correct
11 Correct 154 ms 3036 KB Output is correct
12 Correct 206 ms 3040 KB Output is correct
13 Execution timed out 1065 ms 3308 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 33472 KB Output is correct
2 Correct 150 ms 35104 KB Output is correct
3 Correct 132 ms 33132 KB Output is correct
4 Correct 138 ms 33484 KB Output is correct
5 Correct 146 ms 34252 KB Output is correct
6 Correct 130 ms 33420 KB Output is correct

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 8 ms 2900 KB Output is correct
4 Correct 9 ms 2772 KB Output is correct
5 Correct 6 ms 2772 KB Output is correct
6 Correct 9 ms 2816 KB Output is correct
7 Correct 8 ms 2772 KB Output is correct
8 Correct 193 ms 3028 KB Output is correct
9 Correct 251 ms 3056 KB Output is correct
10 Correct 248 ms 3028 KB Output is correct
11 Correct 154 ms 3036 KB Output is correct
12 Correct 206 ms 3040 KB Output is correct
13 Execution timed out 1065 ms 3308 KB Time limit exceeded
14 Halted 0 ms 0 KB -