oj.uz

답안 #770539

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
770539 2023-07-01T12:45:42 Z vjudge1 Paths (RMI21_paths) C++17
36 / 100
 600 ms 32388 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 9 ms 2772 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 2808 KB Output is correct
7 Correct 10 ms 2804 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 9 ms 2772 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 2808 KB Output is correct
7 Correct 10 ms 2804 KB Output is correct
8 Correct 225 ms 3024 KB Output is correct
9 Correct 322 ms 3152 KB Output is correct
10 Correct 325 ms 3032 KB Output is correct
11 Correct 178 ms 3028 KB Output is correct
12 Correct 226 ms 3024 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 9 ms 2772 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 2808 KB Output is correct
7 Correct 10 ms 2804 KB Output is correct
8 Correct 225 ms 3024 KB Output is correct
9 Correct 322 ms 3152 KB Output is correct
10 Correct 325 ms 3032 KB Output is correct
11 Correct 178 ms 3028 KB Output is correct
12 Correct 226 ms 3024 KB Output is correct
13 Execution timed out 1045 ms 3424 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1077 ms 32388 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 9 ms 2772 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 2808 KB Output is correct
7 Correct 10 ms 2804 KB Output is correct
8 Correct 225 ms 3024 KB Output is correct
9 Correct 322 ms 3152 KB Output is correct
10 Correct 325 ms 3032 KB Output is correct
11 Correct 178 ms 3028 KB Output is correct
12 Correct 226 ms 3024 KB Output is correct
13 Execution timed out 1045 ms 3424 KB Time limit exceeded
14 Halted 0 ms 0 KB -