oj.uz

Submission #770537

# Submission time Handle Problem Language Result Execution time Memory
770537 2023-07-01T12:41:36 Z MohamedFaresNebili Paths (RMI21_paths) C++14
36 / 100
 600 ms 32344 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];
        int ST[400005], lazy[400005];
        int D[100005];
        int X[100005], Y[100005], C[100005];
        int timer, tin[100005], out[100005], id[100005];
        vector<int> adj[100005];

        void update(int v, int l, int r, int p, int 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, int 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, int 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;
        }

        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);
            }
            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;
                int 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] << " ";
                    while(rem[A] == 0) {
                        int B = A;
                        for(int j = 19; j >= 0; j--) {
                            if(rem[par[B][j]] == 0)
                                B = par[B][j];
                        }
                        update(1, 0, N - 1, tin[B], out[B], C[P[B]]);
                        rem[B] = 1;
                    }
                }
                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 9 ms 2812 KB Output is correct
4 Correct 11 ms 2772 KB Output is correct
5 Correct 7 ms 2772 KB Output is correct
6 Correct 13 ms 2816 KB Output is correct
7 Correct 11 ms 2812 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 9 ms 2812 KB Output is correct
4 Correct 11 ms 2772 KB Output is correct
5 Correct 7 ms 2772 KB Output is correct
6 Correct 13 ms 2816 KB Output is correct
7 Correct 11 ms 2812 KB Output is correct
8 Correct 227 ms 3044 KB Output is correct
9 Correct 329 ms 3080 KB Output is correct
10 Correct 326 ms 3048 KB Output is correct
11 Correct 174 ms 3160 KB Output is correct
12 Correct 241 ms 3168 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 9 ms 2812 KB Output is correct
4 Correct 11 ms 2772 KB Output is correct
5 Correct 7 ms 2772 KB Output is correct
6 Correct 13 ms 2816 KB Output is correct
7 Correct 11 ms 2812 KB Output is correct
8 Correct 227 ms 3044 KB Output is correct
9 Correct 329 ms 3080 KB Output is correct
10 Correct 326 ms 3048 KB Output is correct
11 Correct 174 ms 3160 KB Output is correct
12 Correct 241 ms 3168 KB Output is correct
13 Execution timed out 1038 ms 3356 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1079 ms 32344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

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 9 ms 2812 KB Output is correct
4 Correct 11 ms 2772 KB Output is correct
5 Correct 7 ms 2772 KB Output is correct
6 Correct 13 ms 2816 KB Output is correct
7 Correct 11 ms 2812 KB Output is correct
8 Correct 227 ms 3044 KB Output is correct
9 Correct 329 ms 3080 KB Output is correct
10 Correct 326 ms 3048 KB Output is correct
11 Correct 174 ms 3160 KB Output is correct
12 Correct 241 ms 3168 KB Output is correct
13 Execution timed out 1038 ms 3356 KB Time limit exceeded
14 Halted 0 ms 0 KB -