oj.uz

Submission #770541

# Submission time Handle Problem Language Result Execution time Memory
770541 2023-07-01T12:53:07 Z MohamedFaresNebili Paths (RMI21_paths) C++14
48 / 100
 600 ms 37252 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 1 ms 2644 KB Output is correct
2 Correct 2 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 2 ms 2644 KB Output is correct
3 Correct 7 ms 2816 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 2772 KB Output is correct
7 Correct 10 ms 2820 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 2 ms 2644 KB Output is correct
3 Correct 7 ms 2816 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 2772 KB Output is correct
7 Correct 10 ms 2820 KB Output is correct
8 Correct 193 ms 3144 KB Output is correct
9 Correct 251 ms 3072 KB Output is correct
10 Correct 248 ms 3036 KB Output is correct
11 Correct 158 ms 3032 KB Output is correct
12 Correct 196 ms 3028 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 2 ms 2644 KB Output is correct
3 Correct 7 ms 2816 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 2772 KB Output is correct
7 Correct 10 ms 2820 KB Output is correct
8 Correct 193 ms 3144 KB Output is correct
9 Correct 251 ms 3072 KB Output is correct
10 Correct 248 ms 3036 KB Output is correct
11 Correct 158 ms 3032 KB Output is correct
12 Correct 196 ms 3028 KB Output is correct
13 Execution timed out 1067 ms 3324 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 33484 KB Output is correct
2 Correct 181 ms 37252 KB Output is correct
3 Correct 122 ms 35268 KB Output is correct
4 Correct 186 ms 35604 KB Output is correct
5 Correct 160 ms 36308 KB Output is correct
6 Correct 133 ms 35528 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 2 ms 2644 KB Output is correct
3 Correct 7 ms 2816 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 2772 KB Output is correct
7 Correct 10 ms 2820 KB Output is correct
8 Correct 193 ms 3144 KB Output is correct
9 Correct 251 ms 3072 KB Output is correct
10 Correct 248 ms 3036 KB Output is correct
11 Correct 158 ms 3032 KB Output is correct
12 Correct 196 ms 3028 KB Output is correct
13 Execution timed out 1067 ms 3324 KB Time limit exceeded
14 Halted 0 ms 0 KB -