Submission #1214592

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214592		ericl23302	Race (IOI11_race)	C++20	21 / 100	3095 ms	18016 KiB

race

#include "race.h"
#include <bits/stdc++.h>

using namespace std;

int findCentroid(vector<vector<pair<int, int>>> &adjacency, vector<bool> &erased, int cur, int parent, int sz, int &found) {
    bool isCentroid = true;
    int curCount = 1;
    for (auto &[i, j] : adjacency[cur]) {
        if (i == parent || erased[i]) continue;
        int d = findCentroid(adjacency, erased, i, cur, sz, found);
        if (found) return d;
        if (sz < 2 * d) isCentroid = false;
        curCount += d;
    }

    if (sz > 2 * curCount) isCentroid = false;
    if (isCentroid) {
        found = 1;
        return cur;
    }

    return curCount;
}

vector<pair<int, int>> findPathsLengths(vector<vector<pair<int, int>>> &adjacency, vector<bool> &erased, int cur, int parent, int shift) {
    vector<pair<int, int>> res = {{shift, 1}};
    for (auto &[child, length] : adjacency[cur]) {
        if (child == parent || erased[child]) continue;
        vector<pair<int, int>> paths = findPathsLengths(adjacency, erased, child, cur, shift);
        for (auto &[i, j] : paths) res.emplace_back(i + length, j + 1);
    }

    return res;
}

void recurseForSubTree(int N, int K, vector<vector<pair<int, int>>> &adjacency, vector<bool> &erased, int &res, int cur, int sz) {
    int found = 0;
    int centroid = findCentroid(adjacency, erased, cur, -1, sz, found);
    // cout << "CURRENT CENTROID: " << centroid << " IN TREE WITH SIZE: " << sz << " AND RES BEFORE: " << res << endl;
    
    erased[centroid] = true;
    if (sz == 1) return;

    unordered_map<int, int> m;
    m[0] = 0;
    for (auto &[child, length] : adjacency[centroid]) {
        if (erased[child]) continue;
        vector<pair<int, int>> paths = findPathsLengths(adjacency, erased, child, -1, length);
        for (auto &[i, j] : paths) {
            if (m.count(K - i)) res = min(res, j + m[K - i]);
        }

        for (auto &[i, j] : paths) {
            if (m.count(i)) m[i] = min(m[i], j);
            else m[i] = j;
        }
    }
    // cout << "CENTROID: " << centroid << " COMPLETE WITH RES: " << res << endl;
}

void dfs(int cur, int parent, vector<bool> &visited, vector<bool> &erased, vector<vector<pair<int, int>>> &adjacency, int &cnt) {
    ++cnt;
    visited[cur] = true;
    for (auto &[i, j] : adjacency[cur]) {
        if (i == parent || erased[i]) continue;
        dfs(i, cur, visited, erased, adjacency, cnt);
    }
}

bool recurseAllSubtrees(int N, int K, vector<vector<pair<int, int>>> &adjacency, vector<bool> &erased, int &res) {
    bool done = true;
    vector<bool> visited(N, false);
    for (int i = 0; i < N; ++i) {
        if (visited[i] || erased[i]) continue;
        int cnt = 0;
        dfs(i, -1, visited, erased, adjacency, cnt);
        recurseForSubTree(N, K, adjacency, erased, res, i, cnt);
        done = false;
    }

    // cout << "LOOP COMPLETE WITH RES: " << res << ". " << (done ? "ALL COMPLETE. " : "MODIFICATIONS DONE. ") << endl;

    return done;
}

int best_path(int N, int K, int H[][2], int L[])
{
    vector<vector<pair<int, int>>> adjacency(N);
    for (int i = 0; i < N - 1; ++i) {
        adjacency[H[i][0]].emplace_back(H[i][1], L[i]);
        adjacency[H[i][1]].emplace_back(H[i][0], L[i]);
    }

    vector<bool> erased(N, false);
    int res = 1e9;
    
    while (!recurseAllSubtrees(N, K, adjacency, erased, res)) continue;

    return (res < 1e9 ? res : -1);
}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57