oj.uz

Submission #1058895

# Submission time Handle Problem Language Result Execution time Memory
1058895 2024-08-14T14:52:15 Z CodeLakVN Race (IOI11_race) C++17
0 / 100
 6 ms 44124 KB 
#ifndef LAK
#include <race.h>
#endif // LAK

#include <bits/stdc++.h>

#define no "NO"
#define yes "YES"
#define F first
#define S second
#define vec vector
#define task "main"
#define ll long long
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())

using namespace std;

template<typename U, typename V> bool maximize(U &a, V b) {
    if (a < b) { a = b; return 1; } return 0;
}
template<typename U, typename V> bool minimize(U &a, V b) {
    if (a > b) { a = b; return 1; } return 0;
}

const int N = (int)2e5 + 9;
const int INF = (int)1e9;
const int MOD = (int)1e9 + 7;

int numNode, numDist;
vector<ii> adj[N];
vector<int> newADJ[N];
int child[N], high[N], par[N];
bool del[N];
map<int, ll> dist[N];
map<ll, int> firstMin[N], secondMin[N];
int ans = INF;

int countChild(int u, int p) {
    child[u] = 1;
    for (auto [v, w] : adj[u]) {
        if (v == p || del[v]) continue;
        countChild(v, u);
        child[u] += child[v];
    }
    return child[u];
}

int centroid(int u, int p, int m) {
    for (auto [v, w] : adj[u]) {
        if (v == p || del[v]) continue;
        if (child[v] > m / 2) return centroid(v, u, m);
    }
    return u;
}

void calcDist(int u, int p, int root, int cnt) {
    for (auto [v, w] : adj[u]) {
        if (v == p || del[v]) continue;
        dist[root][v] = dist[root][u] + w;
        int curDist = dist[root][v];
        if (!firstMin[root].count(curDist) || firstMin[root][curDist] > cnt + 1)
            firstMin[root][curDist] = cnt + 1;
        else if (!secondMin[root].count(curDist) || secondMin[root][curDist] > cnt + 1)
            secondMin[root][curDist] = cnt + 1;
        calcDist(v, u, root, cnt + 1);
    }
}

int cd(int u) {
    int m = countChild(u, 0);
    u = centroid(u, 0, m);
    del[u] = 1;
    firstMin[u][0] = 0;
    calcDist(u, 0, u, 0);
    for (auto [v, w] : adj[u]) {
        if (del[v]) continue;
        int x = cd(v);
        par[x] = u;
        newADJ[u].push_back(x);
        newADJ[x].push_back(u);
    }
    return u;
}

void initDFS(int u, int p) {
    for (int v : newADJ[u]) {
        if (v == p) continue;
        high[v] = high[u] + 1;
        initDFS(v, u);
    }
}

void calcDFS(int u, int p) {
    int parU = par[u];
    while (parU != -1) {
        int curDist = dist[parU][u];
        int curVertices = high[u] - high[parU];

        if (curDist <= numDist) {
            int remDist = numDist - curDist;
            int remVertices;
            if (!firstMin[parU].count(remDist)) remVertices = -1;
            else {
                if (curDist == remDist)
                    remVertices = (curVertices == firstMin[parU][remDist] ? (secondMin[parU].count(remDist) ? secondMin[parU][remDist] : -1) : firstMin[parU][remDist]);
                else
                    remVertices = firstMin[parU][remDist];
            }
            if (remVertices != -1) minimize(ans, curVertices + remVertices);
        }
        parU = par[parU];
    }

    for (int v : newADJ[u]) {
        if (v == p) continue;
        calcDFS(v, u);
    }
}

int best_path(int n, int k, int h[][2], int l[]) {
    numNode = n;
    numDist = k;
    FOR(i, 0, numNode - 2) {
        int u = h[i][0], v = h[i][1];
        int w = l[i];
        u++;
        v++;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    int root = cd(1);
    par[root] = -1;
    high[root] = 0;
    initDFS(root, -1);
    calcDFS(root, -1);
    return (ans != INF ? ans : -1);
}

#ifdef LAK
int edge[N][2];
int length[N];

void main_code() {
    int numNode, requireDist;
    cin >> numNode >> requireDist;
    FOR(i, 0, numNode - 2) {
        int u, v, l;
        cin >> u >> v >> l;
        edge[i][0] = u, edge[i][1] = v;
        length[i] = l;
    }
    cout << best_path(numNode, requireDist, edge, length);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    const bool MULTITEST = 0;
    int num_test = 1; if (MULTITEST) cin >> num_test;
    while (num_test--) { main_code(); cout << "\n"; }
}
#endif // LAK

/* Lak lu theo dieu nhac */

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 44124 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 44124 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 44124 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 44124 KB Output isn't correct
2 Halted 0 ms 0 KB -