oj.uz

Submission #1108695

# Submission time Handle Problem Language Result Execution time Memory
1108695 2024-11-04T19:16:00 Z _fractal Paths (RMI21_paths) C++14
19 / 100
 600 ms 37204 KB 
#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second 
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define make_unique(x) sort(all(x)), x.erase(unique(all(x)), x.end())

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 Rng(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int N = 1e6 + 200;
const int M = 1e6;
const int inf = 2e9 + 3;
const ll INF = 1e18;

int n, k;
vector<pair<int, int>> g[N];
int cw[N];
long long cost[N];
int anc[N];
int r;

void dfs(int v = r, int p = 0, long long W = 0, int last = 0) {
    anc[v] = p;
    cw[v] = last;
    cost[v] = W;
    for (auto [to, w] : g[v]) {
        if (to == p) continue;
        dfs(to, v, W + w, w);
    }
}

void redfs(int v = r, int p = 0) {
    for (auto [to, w] : g[v]) {
        if (to == p) continue;
        cost[to] = cost[v] + cw[to];
        redfs(to, v);
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> k;
    for (int i = 1, v, u, c; i < n; ++i) {
        cin >> v >> u >> c;
        g[v].emplace_back(u, c);
        g[u].emplace_back(v, c);
    }
    for (r = 1; r <= n; ++r) {
        for (int i = 1; i <= n; ++i) {
            cost[i] = cw[i] = anc[i] = 0;
        }
        dfs();
        long long ans = 0;
        for (int T = 1; T <= k; ++T) {
            int mx = 0;
            for (int i = 1; i <= n; ++i) {
                if (cost[i] > cost[mx])
                    mx = i;
            }
            ans += cost[mx];
            while (mx) {
                cw[mx] = 0;
                mx = anc[mx];
            }
            redfs();
        }
        cout << ans << '\n';
    }
}

Compilation message

Main.cpp: In function 'void dfs(int, int, long long int, int)':
Main.cpp:33:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   33 |     for (auto [to, w] : g[v]) {
      |               ^
Main.cpp: In function 'void redfs(int, int)':
Main.cpp:40:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |     for (auto [to, w] : g[v]) {
      |               ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29008 KB Output is correct
2 Correct 5 ms 29008 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29008 KB Output is correct
2 Correct 5 ms 29008 KB Output is correct
3 Correct 9 ms 29008 KB Output is correct
4 Correct 9 ms 29008 KB Output is correct
5 Correct 9 ms 29008 KB Output is correct
6 Correct 8 ms 29184 KB Output is correct
7 Correct 9 ms 29136 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29008 KB Output is correct
2 Correct 5 ms 29008 KB Output is correct
3 Correct 9 ms 29008 KB Output is correct
4 Correct 9 ms 29008 KB Output is correct
5 Correct 9 ms 29008 KB Output is correct
6 Correct 8 ms 29184 KB Output is correct
7 Correct 9 ms 29136 KB Output is correct
8 Correct 569 ms 29020 KB Output is correct
9 Correct 430 ms 29252 KB Output is correct
10 Correct 397 ms 29008 KB Output is correct
11 Correct 467 ms 29212 KB Output is correct
12 Execution timed out 621 ms 29216 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29008 KB Output is correct
2 Correct 5 ms 29008 KB Output is correct
3 Correct 9 ms 29008 KB Output is correct
4 Correct 9 ms 29008 KB Output is correct
5 Correct 9 ms 29008 KB Output is correct
6 Correct 8 ms 29184 KB Output is correct
7 Correct 9 ms 29136 KB Output is correct
8 Correct 569 ms 29020 KB Output is correct
9 Correct 430 ms 29252 KB Output is correct
10 Correct 397 ms 29008 KB Output is correct
11 Correct 467 ms 29212 KB Output is correct
12 Execution timed out 621 ms 29216 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29008 KB Output is correct
2 Correct 5 ms 29008 KB Output is correct
3 Correct 9 ms 29008 KB Output is correct
4 Correct 9 ms 29008 KB Output is correct
5 Correct 9 ms 29008 KB Output is correct
6 Correct 8 ms 29184 KB Output is correct
7 Correct 9 ms 29136 KB Output is correct
8 Correct 569 ms 29020 KB Output is correct
9 Correct 430 ms 29252 KB Output is correct
10 Correct 397 ms 29008 KB Output is correct
11 Correct 467 ms 29212 KB Output is correct
12 Execution timed out 621 ms 29216 KB Time limit exceeded
13 Halted 0 ms 0 KB -