Submission #429907

#	Time	Username	Problem	Language	Result	Execution time	Memory
429907		Odavey	Race (IOI11_race)	C++17	9 / 100	1084 ms	27400 KiB

race

//
// ~oisín~ C++ Template
//

#include                <bits/stdc++.h>
#define MX_N            200005
#define mp              make_pair
#define mod7            1000000007
#define modpi           314159
#define PI              3.141592653589793238
#define pb              push_back
#define FastIO          ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define All(a)          a.begin(),a.end()
#define fi              first
#define se              second
#define ll              long long int
#define ull             unsigned long long int

int kx[8]  =            {+2, +2, -2, -2, +1, +1, -1, -1};
int ky[8]  =            {+1, -1, +1, -1, +2, -2, +2, -2};
int d9x[9] =            {+1, +1, +1, +0, +0, +0, -1, -1, -1};
int d9y[9] =            {+1, +0, -1, +1, +0, -1, +1, +0, -1};
int dx4[4] =            {+0, +0, +1, -1};
int dy4[4] =            {+1, -1, +0, +0};

ll gcd(ull a, ull b){
    return (a==0)?b:gcd(b%a,a);
}

ll lcm(ull a, ull b){
    return a*(b/gcd(a,b));
}

const long long INF = 1e18;

using namespace std;

map<ll, bool> d_b;
map<ll, int> d_id;
map<int, int> l_q[MX_N];

ll k;

bool is_heavy[MX_N];
int card[MX_N], p[MX_N], heavy[MX_N], l[MX_N], tin[MX_N], tout[MX_N], whom[MX_N*2];
ll depth[MX_N];
int gl_tit = 0;
int gl_dit = 0;

vector<pair<int, ll> > adj[MX_N];

void info_dfs(int at){
    whom[gl_tit] = at;
    tin[at] = gl_tit++;
    card[at] = 1;
    for(auto& [to, w] : adj[at]){
        if(p[at] == to){
            continue;
        }
        p[to] = at;
        l[to] = l[at] + 1;
        depth[to] = depth[at] + w;
        info_dfs(to);
//        card[at] += card[to];
        if(heavy[at] == -1){
            heavy[at] = to;
        }else{
            if(card[to] >= card[heavy[at]]){
                heavy[at] = to;
            }
        }
    }
    if(heavy[at] != -1){
        is_heavy[heavy[at]] = true;
    }
    whom[gl_tit] = -1;
    tout[at] = gl_tit++;
    return;
}

int ans = 1000000009;

void dfs(int at){
    for(auto& [to, w] : adj[at]){
        if(to == p[at] || is_heavy[to]){
            continue;
        }
        dfs(to);
    }
    if(heavy[at] != -1){
        dfs(heavy[at]);
    }
    for(auto& [to, w] : adj[at]){
        if(to == p[at] || is_heavy[to]){
            continue;
        }
        for(int i=tin[to];i<=tout[to];++i){
            if(whom[i] == -1){
                continue;
            }
            if(d_b[depth[whom[i]]] == false){
                l_q[gl_dit][l[whom[i]]]++;
                d_id[depth[whom[i]]] = gl_dit++;
                d_b[depth[whom[i]]] = true;
            }else{
                int tmp_it = d_id[depth[whom[i]]];
                l_q[tmp_it][l[whom[i]]]++;
            }
        }
    }
    if(d_b[depth[at]] == false){
        l_q[gl_dit][l[at]]++;
        d_id[depth[at]] = gl_dit++;
        d_b[depth[at]] = true;
    }else{
        int tmp_it = d_id[depth[at]];
        l_q[tmp_it][l[at]]++;
    }

    for(auto& [to, w] : adj[at]){
        if(to == p[at] || is_heavy[to]){
            continue;
        }
        for(int i=tin[to];i<=tout[to];++i){
            if(whom[i] == -1){
                continue;
            }
            int a = whom[i];
            ll db = k + 2ll*depth[at] - depth[a];
            if(d_b[db] == false){
                continue;
            }
            int tmp_id = d_id[db];
            if(l_q[tmp_id].empty()){
                continue;
            }
            int lb = l_q[tmp_id].begin()->first;
            if(((lb == l[a]) && (l_q[tmp_id][lb] == 1) && depth[a] == db) || (l_q[tmp_id][lb] == 0)){
                continue;
            }
            ans = min(ans, l[a] + lb - 2*l[at]);
        }
    }

    int a = at;
    int tmp_id, lb;
    ll db = k + 2ll*depth[at] - depth[a];
    if(d_b[db] == false){
        goto crime;
    }
    tmp_id = d_id[db];
    if(l_q[tmp_id].empty()){
        goto crime;
    }
    lb = l_q[tmp_id].begin()->first;
    if(((lb == l[a]) && (l_q[tmp_id][lb] == 1) && depth[a] == db) || (l_q[tmp_id][lb] == 0)){
        goto crime;
    }
    ans = min(ans, l[a] + lb - 2*l[at]);

    crime:

    if(!is_heavy[at]){
        for(int i=tin[at];i<=tout[at];++i){
            if(whom[i] == -1){
                continue;
            }
            int tmp_it = d_id[depth[whom[i]]];
            l_q[tmp_it][l[whom[i]]]--;
            if(l_q[tmp_it][l[whom[i]]] == 0){
                l_q[tmp_it].erase(whom[i]);
            }
        }
    }
    return;
}

int best_path(int N, int K, int H[][2], int L[]){
    for(int i=0;i<N-1;++i){
        int u = H[i][0], v = H[i][1];
        ll w = L[i];
        adj[u].pb({v, w});
        adj[v].pb({u, w});
        l_q[i].clear();
    }
    gl_tit = 0;
    gl_dit = 0;
    l_q[N-1].clear();
    d_id.clear();
    d_b.clear();
    memset(whom, -1, sizeof(whom));
    memset(p, -1, sizeof(p));
    memset(heavy, -1, sizeof(heavy));
    memset(is_heavy, 0, sizeof(is_heavy));
    k = K;
    l[0] = 0;
    depth[0] = 0ll;
    info_dfs(0);
    dfs(0);
    if(ans == 1000000009){
        return -1;
    }else{
        return ans;
    }
}

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