Submission #435763

#	Time	Username	Problem	Language	Result	Execution time	Memory
435763		alextodoran	Race (IOI11_race)	C++17	43 / 100	3052 ms	86032 KiB

race

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

**/

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

using namespace std;

typedef long long ll;

const int N_MAX = 100000;

struct Edge
{
    int to;
    int len;
};

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)
    {
        visited.clear();
        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;
        }
        return -1;
    };

    unordered_map <int, int> minEdges[n];
    function <void (int, int, int, int)> get_lens = [&] (int u, int son, int depth, int currLen)
    {
        if(currLen > k)
            return;
        if(minEdges[son].find(currLen) == minEdges[son].end())
            minEdges[son][currLen] = depth;
        else
            minEdges[son][currLen] = min(minEdges[son][currLen], depth);
        for(Edge e : adj[u])
            if(e.to != parent[u] && deleted[e.to] == false)
                get_lens(e.to, son, depth + 1, currLen + e.len);
    };

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

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

        for(Edge e : adj[root])
            get_lens(e.to, e.to, 1, e.len);

        unordered_map <int, int> aux;
        aux[0] = 0;
        for(Edge e : adj[root])
            if(deleted[e.to] == false)
            {
                for(pair <int, int> p : minEdges[e.to])
                {
                    if(aux.find(k - p.first) != aux.end())
                        answer = min(answer, aux[k - p.first] + p.second);
                }
                for(pair <int, int> p : minEdges[e.to])
                {
                    if(aux.find(p.first) == aux.end())
                        aux[p.first] = p.second;
                    else
                        aux[p.first] = min(aux[p.first], p.second);
                }
                minEdges[e.to].clear();
            }

        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: 0 / 57