제출 #349157

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
349157		idk321	경주 (Race) (IOI11_race)	C++11	21 / 100	3094 ms	14080 KiB

race

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

using namespace std;
typedef long long ll;

const int N = 200001;
const int K = 1000001;

vector<array<int, 2>> adj[N];
//int par[N];
int n, k;
bool vis[N];
int dist[K];


int sizOf(int node, int parent)
{
    if (vis[node]) return 0;
    int res = 1;
    for (auto next : adj[node])
    {
        if (next[0] == parent) continue;
        res += sizOf(next[0], node);
    }

    return res;
}

array<int, 2> dfs2(int node, int par, int siz)
{
    if (vis[node]) return {0, -1};

    bool good = true;
    int down = 0;
    for (auto next : adj[node])
    {
        if (next[0] == par) continue;
        auto curr = dfs2(next[0], node, siz);
        if (curr[1] != -1) return {-1, curr[1]};
        if (curr[0] > siz / 2) good = false;
        down += curr[0];
    }

    good = good && ((siz - down - 1) <= siz / 2);
    array<int, 2> res = {down + 1, -1};
    if (good) res[1] = node;
    return res;
}



int dfs1(int node, int parent, int edges, int cdist, vector<array<int, 2>>& cvis)
{
    if (vis[node]) return N;
    if (cdist > k) return N;
    int res = N;
    //cout << node << " a " << cdist << " " << k <<endl;

    res = min(res, edges + dist[k - cdist]);
    cvis.push_back({cdist, edges});
    for (auto next : adj[node])
    {
        if (next[0] == parent) continue;
        res = min(res, dfs1(next[0], node, edges + 1, cdist + next[1], cvis));
    }

    return res;
}

int solveRoot(int node)
{
    if (vis[node]) return N;
    int res = N;
    vector<int> allVis;
    for (auto next : adj[node])
    {
        vector<array<int, 2>> cvis;
        res = min(res, dfs1(next[0], node, 1, next[1], cvis));
        for (auto other : cvis)
        {
            allVis.push_back(other[0]);
            dist[other[0]] = min(dist[other[0]], other[1]);
        }
    }
    for (int other : allVis) dist[other] = N;

    //cout << node << " " << res << endl;
    return res;
}

int solve(int node)
{
    if (vis[node]) return N;
    int res = N;
    int root = dfs2(node, -1, sizOf(node, -1))[1];
    res = min(res, solveRoot(root));
    vis[root] = true;
    for (auto next : adj[root])
    {
        //cout << root << " " << next[0] << endl;
        res = min(res, solve(next[0]));
    }

    return res;
}





int best_path(int n1, int k1, int H[][2], int L[])
{
    n = n1;
    k = k1;

    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]});
    }

    for (int i = 1; i < K; i++) dist[i] = N;
    dist[0] = 0;
    int res = N;
    for (int i = 0; i < n; i++) res = min(res, solveRoot(i));
    if (res == N) return -1;
    return res;
}

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