Submission #1269347

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269347		pedro	Race (IOI11_race)	C++20	21 / 100	3094 ms	26692 KiB

race

#include "race.h"

#include <bits/stdc++.h>
using namespace std;

#define ii pair<int, int>
#define vi vector<int>
#define ll long long
#define vll vector<ll>
#define INF 99999999999999
#define length second

ll n, k, bestSol = INF;
vector<vector<pair<int, ll>>> adj; // node -> {node, length}
vector<pair<int, ll>> smallest; // [lenght] -> {flag, edgeCount}
vector<ii> nodeInfo; // node -> {edgeCount, length}
vi sizes;
vector<bool> wasRoot;
int centroid;

int flag = 0;

void dfs1(int node, int parent, int edgeCount, int lenSum) {
    nodeInfo[node] = {edgeCount, lenSum};

    if (lenSum > k) return;

    ll s = smallest[k-lenSum].first == flag ? smallest[k-lenSum].second : INF;

    if (k - lenSum >= 0 && s + edgeCount < bestSol) {
        bestSol = smallest[k-lenSum].second + edgeCount;
    }

    for (auto child : adj[node]) if (child.first != parent)
        dfs1(child.first, node, edgeCount + 1, lenSum + child.second);
}

void dfs2(int node, int parent) {
    ii info = nodeInfo[node];

    if (info.length > k) return;

    if (smallest[info.length].first != flag || smallest[info.length].second > info.first) {
        smallest[info.length].first = flag;
        smallest[info.length].second = info.first;
    }

    for (auto child : adj[node]) if (child.first != parent)
        dfs2(child.first, node);
}

void subtreeSize(int node, int parent) {
    int s = 1;
    for (int i=0; i<adj[node].size(); i++) if (adj[node][i].first != parent && !wasRoot[adj[node][i].first]) {
        subtreeSize(adj[node][i].first, node);
        s += sizes[adj[node][i].first];
    }
    sizes[node] = s;
}

void findCentroid(int node, int parent, int numVert) {
    centroid = node;

    ii max = { -1, -1 }; // val, node;
    bool isCentroid = true;
    for (int i=0; i<adj[node].size(); i++) if (adj[node][i].first != node && !wasRoot[adj[node][i].first]) {
        if (sizes[adj[node][i].first] > max.first) max = { sizes[adj[node][i].first], adj[node][i].first };
        if (sizes[adj[node][i].first] > numVert / 2) isCentroid = false;
    }
    
    if (!isCentroid) {
        sizes[node] = numVert - sizes[node] + 1;
        findCentroid(max.second, node, numVert);
    }
}

int best_path(int N, int K, int H[][2], int L[]) {

    n = N;
    k = K;

    adj = vector<vector<pair<int, ll>>>(n);
    smallest = vector<pair<int, ll>>(1000001, {0, INF});
    for (int i=0; i<n-1; i++) {
        adj[H[i][0]].push_back({H[i][1], L[i]});
        adj[H[i][1]].push_back({H[i][0], L[i]});
    }

    nodeInfo = vector<ii>(n, {-1, -1});

    queue<int> queue;
    wasRoot = vector<bool>(n, false);

    queue.push(0);
    while (!queue.empty()) {
        int currRoot = queue.front();

        sizes = vi(n, 0);
        subtreeSize(currRoot, -1);
        int numVertSubTree = sizes[currRoot];
        findCentroid(currRoot, -1, numVertSubTree);

        currRoot = centroid;
        wasRoot[currRoot] = true;
        smallest[0] = {flag, 0};
        queue.pop();
        for (auto child : adj[currRoot]) if (!wasRoot[child.first]) {
            queue.push(child.first);
            dfs1(child.first, currRoot, 1, child.second);
            dfs2(child.first, currRoot);
        }

        flag++;
    }

    if (bestSol == INF) return -1;
    else return bestSol;
  
}

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