제출 #435777

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
435777		alextodoran	Race (IOI11_race)	C++17	100 / 100	968 ms	38204 KiB

race

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

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

using namespace std;

typedef long long ll;

const int K_MAX = 1000000;

struct Edge
{
    int to;
    int len;
};

int aux[K_MAX + 2];
int best_path (int n, int k, int edges[][2], int edgeLen[])
{
    vector <Edge> adj[n];
    for(int i = 0; i < n - 1; i++)
    {
        int u = edges[i][0], v = edges[i][1];
        adj[u].push_back(Edge{v, edgeLen[i]});
        adj[v].push_back(Edge{u, edgeLen[i]});
    }

    bool deleted[n];
    for(int u = 0; u < n; u++)
        deleted[u] = false;

    int subSize[n];
    int parent[n];

    vector <int> visited;
    function <void (int)> dfs = [&] (int u)
    {
        visited.push_back(u);

        subSize[u] = 1;
        for(Edge e : adj[u])
            if(e.to != parent[u] && deleted[e.to] == false)
            {
                parent[e.to] = u;
                dfs(e.to);
                subSize[u] += subSize[e.to];
            }
    };

    function <int (int)> find_centroid = [&] (int root)
    {
        parent[root] = -1;
        dfs(root);

        for(int u : visited)
        {
            bool isCentroid = true;
            for(Edge e : adj[u])
                if(e.to != parent[u] && deleted[e.to] == false)
                    isCentroid &= (subSize[e.to] <= subSize[root] / 2);
            if(parent[u] != -1)
                isCentroid &= ((subSize[root] - subSize[u]) <= subSize[root] / 2);
            if(isCentroid == true)
                return u;
        }

        visited.clear();
        return -1;
    };

    vector <pair <int, int>> minEdges;
    function <void (int, int, int)> get_lens = [&] (int u, int depth, int currLen)
    {
        if(currLen > k)
            return;
        minEdges.push_back(make_pair(currLen, depth));
        for(Edge e : adj[u])
            if(e.to != parent[u] && deleted[e.to] == false)
                get_lens(e.to, depth + 1, currLen + e.len);
    };
    for(int i = 1; i <= k; i++)
        aux[i] = INT_MAX;
    aux[0] = 0;

    int answer = INT_MAX;
    function <void (int)> solve = [&] (int root)
    {
        root = find_centroid(root);

        parent[root] = -1;
        dfs(root);
        visited.clear();

        vector <int> changed;
        for(Edge e : adj[root])
            if(deleted[e.to] == false)
            {
                get_lens(e.to, 1, e.len);
                for(pair <int, int> p : minEdges)
                {
                    if(aux[k - p.first] != INT_MAX)
                        answer = min(answer, aux[k - p.first] + p.second);
                }
                for(pair <int, int> p : minEdges)
                {
                    aux[p.first] = min(aux[p.first], p.second);
                    changed.push_back(p.first);
                }
                minEdges.clear();
            }
        for(int i : changed)
            aux[i] = INT_MAX;
        aux[0] = 0;

        deleted[root] = true;
        for(Edge e : adj[root])
            if(deleted[e.to] == false)
                solve(e.to);
    };

    solve(0);

    if(answer == INT_MAX)
        answer = -1;
    return answer;
}

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