oj.uz

Submission #770540

# Submission time Handle Problem Language Result Execution time Memory
770540 2023-07-01T12:47:23 Z MohamedFaresNebili Paths (RMI21_paths) C++14
36 / 100
 600 ms 20940 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];
        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;
        }

        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;
                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 2784 KB Output is correct
4 Correct 10 ms 2780 KB Output is correct
5 Correct 6 ms 2772 KB Output is correct
6 Correct 10 ms 2772 KB Output is correct
7 Correct 11 ms 2776 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 2784 KB Output is correct
4 Correct 10 ms 2780 KB Output is correct
5 Correct 6 ms 2772 KB Output is correct
6 Correct 10 ms 2772 KB Output is correct
7 Correct 11 ms 2776 KB Output is correct
8 Correct 194 ms 2900 KB Output is correct
9 Correct 257 ms 2948 KB Output is correct
10 Correct 256 ms 2912 KB Output is correct
11 Correct 159 ms 2912 KB Output is correct
12 Correct 200 ms 2900 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 2784 KB Output is correct
4 Correct 10 ms 2780 KB Output is correct
5 Correct 6 ms 2772 KB Output is correct
6 Correct 10 ms 2772 KB Output is correct
7 Correct 11 ms 2776 KB Output is correct
8 Correct 194 ms 2900 KB Output is correct
9 Correct 257 ms 2948 KB Output is correct
10 Correct 256 ms 2912 KB Output is correct
11 Correct 159 ms 2912 KB Output is correct
12 Correct 200 ms 2900 KB Output is correct
13 Execution timed out 1074 ms 3064 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 1074 ms 20940 KB Time limit exceeded
2 Halted 0 ms 0 KB -

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 2784 KB Output is correct
4 Correct 10 ms 2780 KB Output is correct
5 Correct 6 ms 2772 KB Output is correct
6 Correct 10 ms 2772 KB Output is correct
7 Correct 11 ms 2776 KB Output is correct
8 Correct 194 ms 2900 KB Output is correct
9 Correct 257 ms 2948 KB Output is correct
10 Correct 256 ms 2912 KB Output is correct
11 Correct 159 ms 2912 KB Output is correct
12 Correct 200 ms 2900 KB Output is correct
13 Execution timed out 1074 ms 3064 KB Time limit exceeded
14 Halted 0 ms 0 KB -