Submission #898834

#	Time	Username	Problem	Language	Result	Execution time	Memory
898834		Sir_Ahmed_Imran	Race (IOI11_race)	C++17	0 / 100	2 ms	12720 KiB

race

                              ///~~~LOTA~~~///
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define ff first
#define ss second
#define ll long long 
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define MAXN 200000
int o,D;
int pwr[18];
int siz[MAXN];
int dpt[MAXN];
int mark[MAXN];
int dept[MAXN];
map<int,int> z;
int par[MAXN][18];
vector<pii> a[MAXN];
pii get_dist(int v,int u){
    int x,y,p,q;
    x=v;
    y=u;
    if(dpt[v]>dpt[u]) swap(v,u);
    for(int i=17;i>=0;i--){
        if(par[v][i]>=0){
            if(dpt[par[v][i]]>=dpt[u])
                v=par[v][i];
        }
    }
    for(int i=17;i>=0;i--){
        if(par[v][i]!=par[u][i]){
            v=par[v][i];
            u=par[v][i];
        }
    } 
    if(v!=u){
        v=par[v][0];
        u=par[u][0];
    }
    p=dept[x]+dept[y]-2*dept[v];
    q=dpt[x]+dpt[y]-2*dpt[v];
    return {p,q};
}
void dfs2(int v,int u,int d){
    siz[v]=1;
    pii pi=get_dist(v,d);
    if(z[D-pi.ff])
        o=min(o,pi.ss+z[D-pi.ff]);
    for(auto& i:a[v]){
        if(i.ff!=u && !mark[i.ff]){
            dfs2(i.ff,v,d);
            siz[v]+=siz[i.ff];
        }
    }
}
void dfs3(int v,int u,int d){
    pii pi=get_dist(v,d);
    z[D-pi.ff]=pi.ss;
    for(auto& i:a[v])
        if(i.ff!=u && !mark[i.ff])
            dfs3(i.ff,v,d);
}
int centroid(int v,int u,int x){
    for(auto& i:a[v]){
        if(!mark[i.ff] && i.ff!=u && siz[i.ff]*2>siz[x])
                return centroid(i.ff,v,u);
    }
    return v;
}
void centroid_decomposition(int v){
    int o=centroid(v,-1,v);
    mark[o]=1;
    for(auto& i:a[o]){
        if(!mark[i.ff]){
            dfs2(i.ff,-1,o);
            dfs3(i.ff,-1,o);
        }
    }
    z.clear();
    for(auto& i:a[o])
        if(!mark[i.ff])
            centroid_decomposition(i.ff);
}
void dfs(int v,int u){
    par[v][0]=u;
    for(auto& i:a[v]){
        if(i.ff==u) continue;
        dpt[i.ff]=dpt[v]+1;
        dept[i.ff]=dept[v]+i.ss;
        dfs(i.ff,v);
    }
}
int best_path(int n,int x,int e[MAXN][2],int l[MAXN]){
    o=n;
    D=x;
    int p,q,r;
    for(int i=0;i<n;i++){
        a[e[i][0]].append({e[i][1],l[i]});
        a[e[i][1]].append({e[i][0],l[i]});
    }
    for(int i=pwr[0]=1;i<18;i++)
        pwr[i]=pwr[i-1]*2;
    dept[0]=0;
    dfs(0,-1);
    for(int i=0;i<18;i++) 
        par[0][i]=-1;
    for(int j=0;j<17;j++)
        for(int i=1;i<n;i++)
            par[i][j+1]=par[max(par[i][j],0)][j];
    for(int i=0;i<n;i++){
        p=i;
        q=0;
        for(int j=17;j>=0;j--){
            if(par[p][j]<0) continue;
            else if(dept[i]-dept[par[p][j]]<=x){
                p=par[p][j];
                q+=pwr[j];
                if(dept[i]-dept[p]==x) o=min(o,q); 
            }
        }
    }
    dfs2(0,-1,0);
    z.clear();
    centroid_decomposition(0);
    if(o==n) return -1;
    return o;
}

Compilation message (stderr)

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:99:13: warning: unused variable 'r' [-Wunused-variable]
   99 |     int p,q,r;
      |             ^

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