oj.uz

Submission #770526

# Submission time Handle Problem Language Result Execution time Memory
770526 2023-07-01T11:57:33 Z vjudge1 Paths (RMI21_paths) C++17
19 / 100
 600 ms 10796 KB 
#include <bits/stdc++.h>

        using namespace std;

        int N, K, P[100005], rem[100005];
        long long D[100005];
        int X[100005], Y[100005], C[100005];
        vector<int> adj[100005];
        void dfs(int v, int p) {
            for(auto u : adj[v]) {
                int nxt = ((X[u] ^ Y[u]) ^ v);
                if(nxt == p) continue;
                P[nxt] = u; dfs(nxt, v);
            }
        }

        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++) {
                dfs(l, l); long long res = 0;
                for(int i = 0; i < K; i++) {
                    queue<int> Q; Q.push(l);
                    for(int j = 1; j <= N; j++)
                        D[j] = -1;
                    D[l] = 0; long long ans = 0; int node = l;
                    while(!Q.empty()) {
                        int A = Q.front(); Q.pop();
                        for(auto u : adj[A]) {
                            int nxt = ((X[u] ^ Y[u]) ^ A);
                            long long dis = (rem[u] ? 0 : C[u]);
                            if(D[nxt] == -1) {
                                D[nxt] = dis + D[A];
                                if(D[nxt] > ans)
                                    ans = D[nxt], node = nxt;
                                Q.push(nxt);
                            }
                        }
                    }
                    while(node != l) {
                        rem[P[node]] = 1;
                        node = (node ^ (X[P[node]] ^ Y[P[node]]));
                    }
                    res += ans;
                }
                for(int l = 0; l < N - 1; l++) rem[l] = 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 2 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 2 ms 2644 KB Output is correct
3 Correct 11 ms 2720 KB Output is correct
4 Correct 10 ms 2688 KB Output is correct
5 Correct 8 ms 2644 KB Output is correct
6 Correct 10 ms 2680 KB Output is correct
7 Correct 14 ms 2720 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 11 ms 2720 KB Output is correct
4 Correct 10 ms 2688 KB Output is correct
5 Correct 8 ms 2644 KB Output is correct
6 Correct 10 ms 2680 KB Output is correct
7 Correct 14 ms 2720 KB Output is correct
8 Execution timed out 1032 ms 2740 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 11 ms 2720 KB Output is correct
4 Correct 10 ms 2688 KB Output is correct
5 Correct 8 ms 2644 KB Output is correct
6 Correct 10 ms 2680 KB Output is correct
7 Correct 14 ms 2720 KB Output is correct
8 Execution timed out 1032 ms 2740 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1057 ms 10796 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 2 ms 2644 KB Output is correct
3 Correct 11 ms 2720 KB Output is correct
4 Correct 10 ms 2688 KB Output is correct
5 Correct 8 ms 2644 KB Output is correct
6 Correct 10 ms 2680 KB Output is correct
7 Correct 14 ms 2720 KB Output is correct
8 Execution timed out 1032 ms 2740 KB Time limit exceeded
9 Halted 0 ms 0 KB -