Submission #824145

#	Time	Username	Problem	Language	Result	Execution time	Memory
824145		YassirSalama	Race (IOI11_race)	C++17	21 / 100	34 ms	4616 KiB

race

#include "race.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define OVL(v,s) for(auto x:v) cout<<x<<s;cout<<endl;
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define pb push_back
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
#define endl "\n"
#define mod 1000000007
const ll INF=1e18;
const int MAXN=3000;
ll depth1[MAXN];
ll depth[MAXN];
const int LOGN=17;
int up[MAXN][LOGN];
vector<vector<pair<int,ll>>> v(MAXN);
void dfs(int node,int par,ll ew=0){
   depth[node]=depth[par]+ew;
   depth1[node]=depth1[par]+1;
   up[node][0]=par;
   for(int i=1;i<LOGN;i++) up[node][i]=up[up[node][i-1]][i-1];
   for(auto x:v[node]) {
     if(x.F!=par) dfs(x.F,node,x.S);
   }
}
int LCA(int a,int b){
  if(depth1[a]<depth1[b]) swap(a,b);
  int d=depth1[a]-depth1[b];
  for(int i=LOGN-1;i>=0;i--){
    if((1<<i)&d) a=up[a][i]; 
  }
  if(a==b) return a;
  for(int i=LOGN-1;i>=0;i--){
    if(up[a][i]!=up[b][i]) a=up[a][i],b=up[b][i];
  }
  return up[a][0];
}
int best_path(int N, int K, int H[][2], int L[])
{
  for(int i=0;i<MAXN;i++) depth1[i]=0,depth[i]=0;
  for(int i=0;i<N-1;i++){
    v[H[i][0]].push_back({H[i][1],L[i]});
    v[H[i][1]].push_back({H[i][0],L[i]});
  }
  dfs(1,1);
  ll ans=INF;
  for(int i=0;i<N;i++){
    for(int j=i+1;j<N;j++){
      if(i^j){
        int l=LCA(i,j);
        ll dist=depth[i]+depth[j]-(ll)2*depth[l];
        // dbg(i,j,dist,l);
        if(dist==K){
          ans=min(ans,depth1[i]+depth1[j]-(ll)2*depth1[l]);
        }
      }
    }
  }
  return (ans==INF?-1:ans);
}

#ifdef IOI
#define MAX_N 500000

static int N, K;
static int H[MAX_N][2];
static int L[MAX_N];
static int solution;

inline 
void my_assert(int e) {if (!e) abort();}

void read_input()
{
  int i;
  my_assert(2==scanf("%d %d",&N,&K));
  for(i=0; i<N-1; i++)
    my_assert(3==scanf("%d %d %d",&H[i][0],&H[i][1],&L[i]));
  my_assert(1==scanf("%d",&solution));
}

int main()
{
  int ans;
  read_input();
  ans = best_path(N,K,H,L);
  if(ans==solution)
    printf("Correct.\n");
  else
    printf("Incorrect. Returned %d, Expected %d.\n",ans,solution);

  return 0;
}

#endif

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