oj.uz

Submission #1079008

# Submission time Handle Problem Language Result Execution time Memory
1079008 2024-08-28T09:21:36 Z coolboy19521 Race (IOI11_race) C++17
0 / 100
 45 ms 66176 KB 
#include "race.h"
#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
#define ll long long
#define int ll

using namespace std;
using namespace __gnu_pbds;

const int sz = 2e5 + 10;

gp_hash_table<int,int> mc[sz], ban;
vector<pair<int,int>> aj[sz];
int ts[sz], k, r;

int uk(int v, int p = -1) {
    ts[v] = 1;
    for (auto& [u, _] : aj[v]) if (u != p)
        ts[v] += uk(u, v);
    return ts[v];
}

int fC(int v, int p = -1) {
    for (auto& [u, _] : aj[v])
        if (u != p && !ban[u])
        if (ts[u] > ts[v] / 2) {
            ts[v] -= ts[u];
            ts[u] += ts[v];
            return fC(u, v);
        }
    return v;
}

void marj(int v, int u) {
    for (auto& [tr, mn] : mc[u])
        if (mc[v].find(tr) != end(mc[v]))
            mc[v][tr] = min(mc[v][tr], mn);
        else mc[v][tr] = mn;
    mc[u].clear();
}

void dfs(int v, int p, int l, int d = 1) {
    mc[v].clear();
    mc[v][l] = d;
    for (auto& [u, w] : aj[v])
        if (u != p && !ban[u]) {
            dfs(u, v, l + w, d + 1);
            if (mc[v].size() < mc[u].size())
                mc[v].swap(mc[u]);
            marj(v, u);
        }
}

void cD(int v) {
    v = fC(v);
    mc[v].clear();
    for (auto& [u, w] : aj[v]) if (!ban[u]) {
        dfs(u, v, w);
        if (mc[v].size() < mc[u].size())
            mc[v].swap(mc[u]);
        for (auto& [tr, mn] : mc[u])
            if (mc[v].find(k - tr) != end(mc[v]))
                r = min(r, mn + mc[v][k - tr]);
        marj(v, u);
    }
    ban[v] = 1;
    for (auto& [u, _] : aj[v])
        if (!ban[u]) cD(u);
}

signed best_path(signed N, signed K, signed H[][2], signed L[]) {
    for (int i = 0; i < N - 1; i ++) {
        int a = H[i][0], b = H[i][1];
        aj[a].emplace_back(b, L[i]);
        aj[b].emplace_back(a, L[i]);
    }
    r = N, k = K;
    uk(0);
    cD(0);
    return r < N ? r : -1;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 66132 KB Output is correct
2 Correct 36 ms 66176 KB Output is correct
3 Correct 41 ms 66064 KB Output is correct
4 Correct 42 ms 65968 KB Output is correct
5 Correct 45 ms 66140 KB Output is correct
6 Correct 42 ms 66128 KB Output is correct
7 Correct 42 ms 66088 KB Output is correct
8 Incorrect 45 ms 66060 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 66132 KB Output is correct
2 Correct 36 ms 66176 KB Output is correct
3 Correct 41 ms 66064 KB Output is correct
4 Correct 42 ms 65968 KB Output is correct
5 Correct 45 ms 66140 KB Output is correct
6 Correct 42 ms 66128 KB Output is correct
7 Correct 42 ms 66088 KB Output is correct
8 Incorrect 45 ms 66060 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 66132 KB Output is correct
2 Correct 36 ms 66176 KB Output is correct
3 Correct 41 ms 66064 KB Output is correct
4 Correct 42 ms 65968 KB Output is correct
5 Correct 45 ms 66140 KB Output is correct
6 Correct 42 ms 66128 KB Output is correct
7 Correct 42 ms 66088 KB Output is correct
8 Incorrect 45 ms 66060 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 66132 KB Output is correct
2 Correct 36 ms 66176 KB Output is correct
3 Correct 41 ms 66064 KB Output is correct
4 Correct 42 ms 65968 KB Output is correct
5 Correct 45 ms 66140 KB Output is correct
6 Correct 42 ms 66128 KB Output is correct
7 Correct 42 ms 66088 KB Output is correct
8 Incorrect 45 ms 66060 KB Output isn't correct
9 Halted 0 ms 0 KB -