제출 #1142116

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1142116		AtabayRajabli	경주 (Race) (IOI11_race)	C++17	0 / 100	2 ms	4932 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
using namespace std;

const int sz = 2e5 + 5, inf = 1e9 + 7;
int n, m, k, ans = inf, w[sz], len[sz], used[sz], par[sz];
long long d[sz];
vector<array<int, 2>> g[sz];
vector<int> cur;
map<long long, int> mp;

void dfs(int v, int p)
{
    w[v] = 1;
    for(auto i : g[v])
    {
        if(i[0] == p) continue;
        dfs(i[0], v);
        w[v] += w[i[0]];                   
    }
}
    
int fnd(int v, int p = 0)
{
    for(auto i : g[v])
    {
        if(i[0] == p || used[i[0]]) continue;
        if(w[i[0]] > w[v] / 2)
        {
            w[v] -= w[i[0]];
            w[i[0]] += w[v];
            return fnd(i[0], v);
        }
    }
    return v;
}

void dist(int v, int p, int cst)
{
    len[v] = len[p] + 1;
    d[v] = d[p] + cst; 
    cur.push_back(v);
    for(auto i : g[v])
    {
        if(i[0] == p || used[i[0]]) continue;
        dist(i[0], v, i[1]);
    }
}

void build(int v)
{
    int c = fnd(v);
    used[c] = 1;
    d[c] = 0;
    len[c] = 0;
    mp[0] = 0;
    for(auto x : g[c])
    {
        int i = x[0];
        if(used[i]) continue;
        cur.clear();
        dist(i, c, x[1]);
        for(int j : cur)
        {
            if(mp.find(k - d[j]) == mp.end()) continue;
            ans = min(ans, mp[k - d[j]] + len[j]);
        }
        for(int j : cur)
        {
            if(mp.find(d[j]) == mp.end()) mp[d[j]] = len[j];
            else mp[d[j]] = min(mp[d[j]], len[j]);
        }
    }
    mp.clear();
    for(auto x : g[c])
    {
        if(used[x[0]]) continue;
        build(x[0]);
    }
}

int best_path(int N, int K, int H[][2], int L[])
{
    n = N, k = K;
    for(int i = 0; i < n - 1; i++)
    {
        int u = H[i][0], v = H[i][1];
        g[u].push_back({v, L[i]});
        g[v].push_back({u, L[i]});
    }
    dfs(1, 1);
    build(1);
    return ans;
}

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