Submission #593485

#	Time	Username	Problem	Language	Result	Execution time	Memory
593485		nguyentu	Race (IOI11_race)	C++14	0 / 100	31 ms	83284 KiB

race

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

#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;

#define ii pair<ll , ll>  
#define iv pair<ii , ii>
#define iii pair<ll , ii>
#define fi first
#define se second
#define ll long long
const ll inf = 1e18 + 7;
const ll MAX_N = 2e5 + 7;
const ll MOD = 1e9 + 7;
const ll MAX_VAL = 1e7 + 7;

map<ll , ll> cnt;
map<ll , ll> tmp; 
ll n , k;
vector<ii> adj[MAX_N];
bool check[MAX_N];
ll f[MAX_N] , dp[MAX_N] , g[MAX_N];
ll lowest_K[MAX_VAL];
ll low[MAX_VAL];

void DFS(ll u , ll father) {
    f[u] = 1;
    for (auto edge : adj[u]) {
        ll v = edge.fi;
        if (v != father && !check[v]) {
            DFS(v , u);
            f[u] += f[v];
        }
    }
    return;
}

ll find_centroid(ll u , ll father , ll root){
    for (auto edge : adj[u]) {
        ll v = edge.fi;
        if (!check[v] && v != father && 2*f[v] >= f[root]) {
            return find_centroid(v , u , root);
        }
    }
    return u;
}

void DFS1(ll u , ll father) {
    if (dp[u] <= k && g[u] < low[dp[u]]) {
        low[dp[u]] = g[u];
        cnt[dp[u]] = 1;
    }
    else if (dp[u] <= k && g[u] == low[dp[u]]) {
        cnt[dp[u]]++;
    }
    for (auto edge : adj[u]) {
        ll v = edge.fi , w = edge.se;
        if (v != father && !check[v]) {
            dp[v] = dp[u] + w;
            g[v] = g[u] + 1;
            DFS1(v , u);
        }
    }   
    return;
}

void DFS2(ll u , ll father) {
    if (dp[u] <= k && g[u] == low[dp[u]]) {
        tmp[dp[u]]++;
    }
    for (auto edge : adj[u]) {
        ll v = edge.fi;
        if (v != father && !check[v]) {
            DFS2(v , u);
        }
    }
}

void centroid(ll u , ll father) {
    DFS(u , u);
    u = find_centroid(u , u , u); 
    cnt.clear();
    dp[u] = 0;
    g[u] = 0;
    DFS1(u , u);
    for (auto it : cnt) {
        ll x = k - it.fi;
        if (x < 0 || it.fi > k || x > k) continue;
        ll val = it.se; 
        if (it.fi == x) {
            ll tmp1 = low[it.fi];
            if (tmp1 != inf) { 
                ll num = 2*tmp1;
                lowest_K[num] += val*(val - 1);
            }
        }
        else {
            ll tmp1 = low[it.fi] ,tmp2 = low[x];
            if (tmp1 != inf && tmp2 != inf) {
                ll num = tmp1 + tmp2;
                lowest_K[num] += val*cnt[x];
            }
        }
    }   
    check[u] = 1;
    for (auto edge : adj[u]) {
        ll v = edge.fi;
        if (v != father && !check[v]) {
            tmp.clear();
            DFS2(v , v);
            for (auto it : tmp) {
                ll x = k - it.fi;
                if (x < 0 || it.fi > k || x > k) continue;
                ll val = it.se;
                if (it.fi == x) {
                    ll tmp1 = low[it.fi];
                    if (tmp1 != inf) { 
                        ll num = 2*tmp1;
                        lowest_K[num] -= val*(val - 1);
                    }
                }
                else {
                    ll tmp1 = low[it.fi] ,tmp2 = low[x];
                    if (tmp1 != inf && tmp2 != inf) {
                        ll num = tmp1 + tmp2;
                        lowest_K[num] -= val*tmp[x];
                    }
                }
            }
        }
    }  
    for (auto edge : adj[u]) {
        ll v = edge.fi;
        if (v != father && !check[v]) {
            centroid(v , u);
        }
    }
}

int best_path(int N, int K, int H[][2], int L[]){   
    n = N , k = K;
    for (ll i = 0 ; i < (n - 1) ; i++) {
        adj[H[i][0] + 1].push_back(ii(H[i][1] + 1 , L[i]));
        adj[H[i][1]+1].push_back(ii(H[i][0]+1 , L[i]));
    }
    for (ll i = 0 ; i < MAX_VAL ; i++) {
        low[i] = inf;
    }
    centroid(1 , -1);
    for (ll i = 0 ; i < MAX_VAL ; i++) {
        if (lowest_K[i]) {
            return i;
        }
    }
    return -1;
}

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