Submission #541525

#	Time	Username	Problem	Language	Result	Execution time	Memory
541525		georgerapeanu	Race (IOI11_race)	C++11	9 / 100	124 ms	10324 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 dfs_add(int nod, int tata){
  if(mp.count(lvl_cost[nod]) == 0){
    mp[lvl_cost[nod]] = 1 << 30;
  }
  mp[lvl_cost[nod]] = min(mp[lvl_cost[nod]], lvl[nod]);
  for(auto it:graph[nod]){
    if(it.first == tata){
      continue;
    }
    dfs_add(it.first, nod);
  }
}

int ans_length = (1 << 30);

void dfs_view(int root, int nod, int tata){
  long long target = k - (lvl_cost[nod] - lvl_cost[root]) + lvl_cost[nod];
  //cerr << root << " " << nod << " with costs " << lvl_cost[root] << " " << lvl_cost[nod] << " looking for " << target << endl;
  if(mp.count(target)){
    ans_length = min(ans_length, lvl[nod] + mp[target] - 2 * lvl[root]); 
    //cerr << "ans2 length updated to " << ans_length << endl;
  }
  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);
  }
  for(auto it:graph[nod]){
    if(it.first == tata || it.first == heavyChild){
      continue;
    }
    dfs_view(nod, it.first, nod);
    dfs_add(it.first, nod);
  }

  if(mp.count(lvl_cost[nod]) == 0){
    mp[lvl_cost[nod]] = 1 << 30;
  }
  mp[lvl_cost[nod]] = min(mp[lvl_cost[nod]], lvl[nod]);
  
 // cerr << nod << "looking down for " << lvl_cost[nod] + k << endl;
//  cerr << "big child is " << heavyChild << endl;
//  cerr << "level cost is " << lvl_cost[nod] << endl;
//  cerr << "k is " << k << endl;
//  for(auto it:mp){
//    cerr << "debuggg " << it.first << " " << it.second << endl; 
//  }
  if(mp.count(lvl_cost[nod] + k)){
    //cerr << "found " << mp[lvl_cost[nod] + k] << endl;
    ans_length = min(ans_length, mp[lvl_cost[nod] + k] - lvl[nod]);
  //  cerr << "ans length updated to " << ans_length << endl;
  }
  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++){
    //cerr << "edge " << h[i][0] + 1 << " " << h[i][1] + 1 << " " << l[i] << endl;
    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);
  for(int i = 1;i <= n;i++){
   // cerr << "debug " << weight[i] << " " << lvl[i] << " " << lvl_cost[i] << endl;
  }
  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