제출 #765435

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
765435		vjudge1	경주 (Race) (IOI11_race)	C++17	100 / 100	770 ms	40240 KiB

race

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

#define el '\n'
#define FIO ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned uint;
typedef __int128 bint;
typedef long double ld;
typedef complex<ld> pt;
typedef unsigned long long ull;

template<typename T, typename X>
using hashTable = gp_hash_table<T, X>;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

// mt19937_64 for unsigned long long
mt19937 rng(std::chrono::system_clock::now().time_since_epoch().count());

const int N = 2e5 + 5;

int sz[N];
int k, ans;
bool vis[N];
map<int, int> ht;
vector<pair<int, int>> G[N];

int dfsSZ(int node, int par = -1)
{
    sz[node] = 1;
    for(auto &[ch, w]: G[node])
    {
        if(ch == par || vis[node])
            continue;
        sz[node] += dfsSZ(ch, node);
    }
    return sz[node];
}

int getCentroid(int node, int par, int &n)
{
    for(auto &[ch, w]: G[node])
    {
        if(ch == par || vis[ch])
            continue;

        if(sz[ch] << 1 > n)
            return getCentroid(ch, node, n);
    }
    return node;
}

int query(int node, int par, int dep, int tot)
{
    if(tot > k)
        return 1e9;

    int ret = (ht.find(k - tot) != ht.end() ? dep + ht[k - tot] : 1e9);
    for(auto &[ch, w]: G[node])
    {
        if(ch == par || vis[ch])
            continue;
        ret = min(ret, query(ch, node, dep + 1, tot + w));
    }
    return ret;
}

void update(int node, int par, int dep, int tot)
{
    if(tot > k)
        return;

    if(ht.find(tot) != ht.end())
        ht[tot] = min(ht[tot], dep);
    else
        ht[tot] = dep;

    for(auto &[ch, w]: G[node])
    {
        if(ch == par || vis[ch])
            continue;
        update(ch, node, dep + 1, tot + w);
    }
}

void solveSubTree(int centroid, int par)
{
    ht.clear(), ht[0] = 0;
    for(auto &[ch, w]: G[centroid])
    {
        if(ch == par || vis[ch])
            continue;

        ans = min(ans, query(ch, centroid, 1, w));
        update(ch, centroid, 1, w);
    }
}

void decompose(int node, int par)
{
    dfsSZ(node, par);
    int centroid = getCentroid(node, par, sz[node]);

    vis[centroid] = true;
    solveSubTree(centroid, par);
    for(auto &[ch, w]: G[centroid])
    {
        if(ch == par || vis[ch])
            continue;
        decompose(ch, centroid);
    }
}

int best_path(int n, int K, int H[][2], int L[])
{
    for(int i = 0; i < n; i++)
        G[i].clear(), vis[i] = 0;

    k = K, ans = 1e9;
    vector<pair<pair<int, int>, int>> e;
    for(int i = 0; i < n - 1; i++)
    {
        e.push_back({{H[i][0], H[i][1]}, L[i]});
        if(L[i] == k)
            return 1;
    }

    for(auto &[p, w]: e)
        G[p.first].emplace_back(p.second, w), G[p.second].emplace_back(p.first, w);

    decompose(0, -1);
    return (ans == 1e9 ? -1 : ans);
}

//void doWork()
//{
//    int n, K;
//    cin >> n >> K;
//    int H[n][2], L[n];
//    for(int i = 0; i < n - 1; i++)
//        cin >> H[i][0] >> H[i][1];
//    for(int i = 0; i < n - 1; i++)
//        cin >> L[i];
//
//    cout << best_path(n, K, H, L);
//}
//
//signed main()
//{
//    FIO
//    int T = 1;
////    cin >> T;
//    for(int i = 1; i <= T; i++)
//        doWork();
//}
/*

4 3
0 1
1 2
1 3
1 2 4


3 3
0 1
1 2
1 1



11 12
0 1
0 2
2 3
3 4
4 5
0 6
6 7
6 8
8 9
8 10
3 4 5 4 6 3 2 5 6 7

 */

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