oj.uz

Submission #770538

# Submission time Handle Problem Language Result Execution time Memory
770538 2023-07-01T12:45:12 Z MohamedFaresNebili Paths (RMI21_paths) C++14
36 / 100
 600 ms 32428 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] << " ";
                    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 2772 KB Output is correct
4 Correct 11 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 2804 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 2772 KB Output is correct
4 Correct 11 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 2804 KB Output is correct
8 Correct 197 ms 3020 KB Output is correct
9 Correct 246 ms 3064 KB Output is correct
10 Correct 252 ms 3032 KB Output is correct
11 Correct 154 ms 3028 KB Output is correct
12 Correct 190 ms 3020 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 2772 KB Output is correct
4 Correct 11 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 2804 KB Output is correct
8 Correct 197 ms 3020 KB Output is correct
9 Correct 246 ms 3064 KB Output is correct
10 Correct 252 ms 3032 KB Output is correct
11 Correct 154 ms 3028 KB Output is correct
12 Correct 190 ms 3020 KB Output is correct
13 Execution timed out 1075 ms 3320 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 1082 ms 32428 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 7 ms 2772 KB Output is correct
4 Correct 11 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 2804 KB Output is correct
8 Correct 197 ms 3020 KB Output is correct
9 Correct 246 ms 3064 KB Output is correct
10 Correct 252 ms 3032 KB Output is correct
11 Correct 154 ms 3028 KB Output is correct
12 Correct 190 ms 3020 KB Output is correct
13 Execution timed out 1075 ms 3320 KB Time limit exceeded
14 Halted 0 ms 0 KB -