Submission #1049122

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049122		beaconmc	Race (IOI11_race)	C++14	21 / 100	3031 ms	96800 KiB

race

#include "race.h"
#include <bits/stdc++.h>
 
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)

using namespace std;

const ll maxn = 200005;
const ll INF = 1000000000;

vector<vector<ll>> edges[maxn];
ll par[maxn];
ll centpar[maxn];
ll depth[maxn];
ll realdepth[maxn];
ll ancc[maxn][20];
bool visited[maxn];
ll sub[maxn];

ll anc(ll a, ll x){
    if (a==0) return 0;
    if (x==0) return par[a];
    if (ancc[a][x] != -1) return ancc[a][x];
    return ancc[a][x] = anc(anc(a,x-1),x-1);
}

ll lca(ll a, ll b){
    if (depth[a] < depth[b]) swap(a,b);
    FORNEG(i,19,-1) if (depth[anc(a, i)] >= depth[b]) a = anc(a,i);
    if (a==b) return a;
    FORNEG(i,19,-1) if (anc(a,i) != anc(b,i)) a = anc(a,i), b = anc(b,i);
    return par[a];
}

void initdfs(ll a,ll p, ll d, ll dd){
    par[a] = p;
    depth[a] = d;
    realdepth[a] = dd;
    for (auto&i : edges[a]){
        if (i[0] != p) initdfs(i[0], a, d+1, dd+i[1]);
    }
}

ll centroid(ll root, ll a, ll p){
    for (auto&i : edges[a]){
        if (!visited[i[0]] && i[0] != p) return centroid(root, i[0], a);
    }
    return a;
}
void dfs(ll a, ll p){
    sub[a] = 1;
    for (auto&i : edges[a]) if(i[0] != p && !visited[i[0]]) dfs(i[0], a), sub[a] += sub[i[0]];
}
void build(ll a, ll p){
    dfs(a,p);
    ll cent = centroid(a, a, p);
    centpar[cent] = p;
    visited[cent] = 1;
    for (auto&i : edges[cent]){
        if (!visited[i[0]]) build(i[0], cent);
    }
}

map<ll, pair<array<ll,2>,array<ll,2>>> dists[maxn];

int best_path(int N, int K, int H[][2], int L[])
{
    FOR(i,0,maxn) par[i] = -1, centpar[i] = -1, par[i] -1, depth[i] = -1, realdepth[i] = -1,dists[i].clear();
    FOR(i,0,maxn)FOR(j,0,30) ancc[i][j] = -1;
    FOR(i,0,N){
        edges[H[i][0]].push_back({H[i][1], L[i]});
        edges[H[i][1]].push_back({H[i][0], L[i]});
    }
    initdfs(0,-1,0,0);
    build(0,-1);

    FOR(i,0,N){
        ll temp = centpar[i];
        ll prev = i;

        while (temp != -1){
            ll idk = lca(temp,i);
            ll cur = depth[temp] + depth[i] - depth[idk]*2;
           
            ll dist = realdepth[temp] + realdepth[i] - realdepth[idk]*2;

            if (dists[temp].count(dist) == 0) dists[temp][dist] = make_pair(array<ll,2>{cur, prev}, array<ll,2>{INF, INF});
            else{
                array<ll,2> a,b;
                a = dists[temp][dist].first;
                b = dists[temp][dist].second;

                if (a[1] == prev){
                    a[0] = min(a[0], cur);
                }else if (b[1] == prev){
                    b[0] = min(b[0], cur);
                }else{
                    if (cur <= a[0]) b = a, a = {cur, prev};
                    else if (cur <= b[0]) b = {cur, prev};
                }
                if (a[0] > b[0]) swap(a,b);
                dists[temp][dist] = make_pair(a,b);
            }
            prev = temp;
            temp = centpar[temp];

        }
    }
    ll ans = INF;
    FOR(i,0,N){
        for (auto&k : dists[i]){
            ll req = K-k.first;
            if (req == 0) ans = min(ans, k.second.first[0]);


            if (dists[i].count(req)==0) continue;
            if (req == k.first){

                ans = min(ans, k.second.first[0]+k.second.second[0]);
            }
            else{

                // cout << k.second.first[0] << " " << k.second.first[1] << endl;
                // cout << dists[i][req].first[0] << " " << dists[i][req].first[1] << endl;

                if (k.second.first[1] != dists[i][req].first[1]) ans = min(ans, k.second.first[0] + dists[i][req].first[0]);
                if (k.second.first[1] != dists[i][req].second[1]) ans = min(ans, k.second.first[0] + dists[i][req].second[0]);
                if (k.second.second[1] != dists[i][req].first[1]) ans = min(ans, k.second.second[0] + dists[i][req].first[0]);
                if (k.second.second[1] != dists[i][req].second[1]) ans = min(ans, k.second.second[0] + dists[i][req].second[0]);
            }
        }
    }

    if (ans >= INF) return -1;
    else return ans;

}

Compilation message (stderr)

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:70:56: warning: right operand of comma operator has no effect [-Wunused-value]
   70 |     FOR(i,0,maxn) par[i] = -1, centpar[i] = -1, par[i] -1, depth[i] = -1, realdepth[i] = -1,dists[i].clear();
      |                                                 ~~~~~~~^~
race.cpp:71:41: warning: iteration 20 invokes undefined behavior [-Waggressive-loop-optimizations]
   71 |     FOR(i,0,maxn)FOR(j,0,30) ancc[i][j] = -1;
      |                              ~~~~~~~~~~~^~~~
race.cpp:5:33: note: within this loop
    5 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
   71 |     FOR(i,0,maxn)FOR(j,0,30) ancc[i][j] = -1;
      |                      ~~~~~~      
race.cpp:71:18: note: in expansion of macro 'FOR'
   71 |     FOR(i,0,maxn)FOR(j,0,30) ancc[i][j] = -1;
      |                  ^~~

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