Submission #541573

#	Time	Username	Problem	Language	Result	Execution time	Memory
541573		georgerapeanu	Race (IOI11_race)	C++11	9 / 100	112 ms	9040 KiB

race

#include "race.h"

#pragma once
#include <bits/stdc++.h>
using namespace std;

int n, k;
vector<vector<pair<int, int> > > graph;
vector<int> lvl;
vector<long long> lvl_cost;
vector<int> weight;

void predfs(int nod, int tata){
  for(auto it:graph[nod]){
    if(it.first == tata){
      continue;
    }
    lvl[it.first] = 1 + lvl[nod];
    lvl_cost[it.first] = it.second + lvl_cost[nod];
    predfs(it.first, nod);
    weight[nod] += weight[it.first];
  }
}

unordered_map<long long, int> mp;

void add(int nod){
  if(mp.count(lvl_cost[nod]) == 0){
    mp[lvl_cost[nod]] = lvl[nod];
  }else{
    mp[lvl_cost[nod]] = min(mp[lvl_cost[nod]], lvl[nod]);
  }
}

int ans_length = (1 << 30);

void update(long long target, int root, int nod){
  if(mp.count(target) == 0){
    return ;
  }
  ans_length = min(ans_length, mp[target] + lvl[nod] - 2 * lvl[root]);
}


void dfs_add(int nod, int tata){
  add(nod);
  for(auto it:graph[nod]){
    if(it.first == tata){
      continue;
    }
    dfs_add(it.first, nod);
  }
}

void dfs_view(int root, int nod, int tata){
  long long target = k - (lvl_cost[nod] - lvl_cost[root]) + lvl_cost[nod];
  update(target, root, nod);
  for(auto it:graph[nod]){
    if(it.first == tata){
      continue;
    }
    dfs_view(root, it.first, nod);
  }
}

void dfs(int nod, int tata, bool dump){ 
  int heavyChild = -1;
  for(auto it:graph[nod]){
    if(it.first == tata){
      continue;
    }
    if(heavyChild == -1 || weight[it.first] > weight[heavyChild]){
      heavyChild = it.first;
    }
  }

  for(auto it:graph[nod]){
    if(it.first == tata || it.first == heavyChild){
      continue;
    }
    dfs(it.first, nod, true);
  }
  if(heavyChild != -1){
    dfs(heavyChild, nod, false);
  }
  add(nod);
  for(auto it:graph[nod]){
    if(it.first == tata || it.first == heavyChild){
      continue;
    }
    dfs_view(nod, it.first, nod);
    dfs_add(it.first, nod);
  }

  update(lvl_cost[nod] + k, nod, nod);

  
  if(dump){
    mp.clear();
  }
}

int best_path(int _n, int _k, int h[][2], int l[]){
  n = _n;
  k = _k;
  graph = vector<vector<pair<int,int> > >(n + 1, vector<pair<int, int> >());
  lvl = vector<int>(n + 1,0);
  lvl_cost = vector<long long>(n + 1, 0);
  weight = vector<int>(n + 1, 1);
  for(int i = 0;i < n - 1;i++){
    graph[h[i][0] + 1].push_back({h[i][1] + 1, l[i]});
    graph[h[i][1] + 1].push_back({h[i][0] + 1, l[i]});
  }

  predfs(1, 0);
  dfs(1, 0, true);
  
  return (ans_length == (1 << 30) ? -1:ans_length);
}

Compilation message (stderr)

race.cpp:3:9: warning: #pragma once in main file
    3 | #pragma once
      |         ^~~~

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