Submission #672397

#	Time	Username	Problem	Language	Result	Execution time	Memory
672397		vjudge1	Race (IOI11_race)	C++17	43 / 100	3077 ms	106424 KiB

race

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;


typedef long long ll;


const int N = 200100;

vector<int> sz(N);
vector<bool> vis(N);
int ans = 1000000000;
ll k;
map<ll, int> mn;
vector<pair<int, ll>> 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] * 2 > n)
            return getCentroid(ch, node, n);
    }
    return node;
}

int curHead;
vector<pair<ll, int>> pool[N];

void dfs(int node, int par, ll dist, int dep)
{
    pool[curHead].emplace_back(dist, dep);
    for(auto &[ch, w]: G[node])
    {
        if(ch == par || vis[ch])
            continue;
        dfs(ch, node, dist + w, dep + 1);
    }
}


void decompose(int node = 0)
{
    int centroid = getCentroid(node, -1, dfsSZ(node));

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

        curHead++;
        dfs(ch, centroid, w, 1);
        for(auto &[dis, dep]: pool[curHead])
        {
            if(dis == k || mn[k - dis])
                ans = min(ans, dep + mn[k - dis]);
        }
        for(auto &[dis, dep]: pool[curHead])
        {
            if(!mn[dis])
                mn[dis] = dep;
            mn[dis] = min(mn[dis], dep);
        }
    }
    mn.clear();
    for(auto &[ch, w]: G[centroid])
    {
        if(vis[ch])
            continue;
        decompose(ch);
    }
}

int best_path(int n, int K, int H[][2], int L[])
{
    k = K, ans = 1000000000;
    for(int i = 0; i < n - 1; i++)
    {
        G[H[i][0]].emplace_back(H[i][1], L[i]);
        G[H[i][1]].emplace_back(H[i][0], L[i]);

        if(L[i] == k)
            return 1;
    }

    decompose();
    return (ans == 1000000000 ? -1 : ans);
}
//
//int main()
//{
//    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);
//}

/*

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