oj.uz

Submission #770547

# Submission time Handle Problem Language Result Execution time Memory
770547 2023-07-01T13:03:24 Z MohamedFaresNebili Paths (RMI21_paths) C++14
48 / 100
 600 ms 24380 KB 
#include <bits/stdc++.h>

        using namespace std;
        using ll = long long;

        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) {
            if(l > hi || r < lo) return;
            if(l >= lo && r <= hi) {
                ST[v] -= val; lazy[v] += val;
                ///prop(v, l, r);
                return;
            }
            prop(v, l, r);
            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++) {
                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 < 11; 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 = 10; 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 1 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 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 6 ms 2776 KB Output is correct
4 Correct 8 ms 2772 KB Output is correct
5 Correct 5 ms 2772 KB Output is correct
6 Correct 8 ms 2788 KB Output is correct
7 Correct 7 ms 2772 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 6 ms 2776 KB Output is correct
4 Correct 8 ms 2772 KB Output is correct
5 Correct 5 ms 2772 KB Output is correct
6 Correct 8 ms 2788 KB Output is correct
7 Correct 7 ms 2772 KB Output is correct
8 Correct 172 ms 2924 KB Output is correct
9 Correct 249 ms 2900 KB Output is correct
10 Correct 225 ms 3048 KB Output is correct
11 Correct 135 ms 2916 KB Output is correct
12 Correct 169 ms 2904 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 6 ms 2776 KB Output is correct
4 Correct 8 ms 2772 KB Output is correct
5 Correct 5 ms 2772 KB Output is correct
6 Correct 8 ms 2788 KB Output is correct
7 Correct 7 ms 2772 KB Output is correct
8 Correct 172 ms 2924 KB Output is correct
9 Correct 249 ms 2900 KB Output is correct
10 Correct 225 ms 3048 KB Output is correct
11 Correct 135 ms 2916 KB Output is correct
12 Correct 169 ms 2904 KB Output is correct
13 Execution timed out 1048 ms 3208 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 22428 KB Output is correct
2 Correct 122 ms 24380 KB Output is correct
3 Correct 105 ms 22440 KB Output is correct
4 Correct 148 ms 22412 KB Output is correct
5 Correct 151 ms 23276 KB Output is correct
6 Correct 105 ms 22476 KB Output is correct

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 6 ms 2776 KB Output is correct
4 Correct 8 ms 2772 KB Output is correct
5 Correct 5 ms 2772 KB Output is correct
6 Correct 8 ms 2788 KB Output is correct
7 Correct 7 ms 2772 KB Output is correct
8 Correct 172 ms 2924 KB Output is correct
9 Correct 249 ms 2900 KB Output is correct
10 Correct 225 ms 3048 KB Output is correct
11 Correct 135 ms 2916 KB Output is correct
12 Correct 169 ms 2904 KB Output is correct
13 Execution timed out 1048 ms 3208 KB Time limit exceeded
14 Halted 0 ms 0 KB -