Submission #898812

#	Time	Username	Problem	Language	Result	Execution time	Memory
898812		Sir_Ahmed_Imran	Race (IOI11_race)	C++17	9 / 100	67 ms	26828 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;
int pwr[18];
int siz[MAXN];
int mark[MAXN];
int dept[MAXN];
int par[MAXN][18];
vector<pii> a[MAXN];
void dfs(int v,int u){
    par[v][0]=u;
    for(auto& i:a[v]){
        if(i.ff==u) continue;
        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;
    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); 
            }
        }
    }
    if(o==n) return -1;
    return o;
}

Compilation message (stderr)

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

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