Submission #429451

#	Time	Username	Problem	Language	Result	Execution time	Memory
429451		Odavey	Race (IOI11_race)	C++17	9 / 100	1088 ms	38980 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;
        heavy[at] = -1;
        is_heavy[at] = false;
        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);
            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;
                }
                //cout << "With god as my witness, a = " << a << ", db & lb = " << db << " & " << lb << ", giving " << l[a] + lb - 2*l[at] << " length(s)\n";
                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;
        }
        //cout << "With god as my witness, a = " << a << ", db & lb = " << db << " & " << lb << ", giving " << l[a] + lb - 2*l[at] << " length(s)\n";
        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]]]--;
            }
        }
        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});
        }
        k = K;
        l[0] = 0;
        depth[0] = 0;
        info_dfs(0);
        dfs(0);
      	if(ans == 1000000009){
          	return -1;
        }
        return ans;
    }

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