Submission #749146

#	Time	Username	Problem	Language	Result	Execution time	Memory
749146		anaduguleanu	Race (IOI11_race)	C++14	100 / 100	1527 ms	52488 KiB

race

#include <iostream>
#include <vector>
#include <map>
#define NMAX 200000
#define INF 1000000000000000000
using namespace std;
///ifstream cin ("c.in");
///ofstream cout ("c.out");
vector <pair <int, int>> graph[NMAX + 10];
map <long long, long long> mp;
int ok, mark[NMAX + 10], sz[NMAX + 10];
long long k, ans = INF;
void solve(int node, int parent, long long depth, long long cost)
{
    if (cost > k)
        return;
    if (ok == 1)
    {
        if (mp[cost] == 0)
            mp[cost] = depth;
        else
            mp[cost] = min(mp[cost], depth);
    }
    else
    {
        if (mp[k - cost] != 0)
            ans = min(ans, depth + mp[k - cost] - 2);
    }
    for (auto it: graph[node])
        if (it.first != parent && mark[it.first] == 0)
            solve(it.first, node, depth + 1, cost + it.second);
}
int findCentroid(int node, int s, int parent)
{
    for (auto it: graph[node])
        if (it.first != parent && mark[it.first] == 0 && sz[it.first] * 2 > s)
            return findCentroid(it.first, s, node);
    return node;
}
int dfs(int node, int parent)
{
    sz[node] = 1;
    for (auto it: graph[node])
        if (it.first != parent && mark[it.first] == 0)
            sz[node] = sz[node] + dfs(it.first, node);
    return sz[node];
}
void centroid(int node)
{
    int aux = dfs(node, -1), cent = findCentroid(node, aux, -1);
    mp.clear();
    mp[0] = 1;
    mark[cent] = 1;
    for (auto it: graph[cent])
        if (mark[it.first] == 0)
        {
            ok = 0;
            solve(it.first, -1, 2, it.second);
            ok = 1;
            solve(it.first, -1, 2, it.second);
        }
    for (auto it: graph[cent])
        if (mark[it.first] == 0)
            centroid(it.first);
}
int best_path(int N, int K, int H[][2],int L[])
{
    k = K;
    for (int i = 0; i < N - 1; i++)
    {
        graph[H[i][0] + 1].push_back({H[i][1] + 1, L[i]});
        graph[H[i][1] + 1].push_back({H[i][0] + 1, L[i]});
    }
    centroid(1);
    if (ans == INF)
        return -1;
    else
        return ans;
}

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