Submission #849012

#	Time	Username	Problem	Language	Result	Execution time	Memory
849012		BidoTeima	Race (IOI11_race)	C++17	0 / 100	3 ms	14424 KiB

race

//#pragma once
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 3;
int k;
vector<pair<int,int>>adj[N];
bool marked[N];
int sub[N];
int sz;
int ans = 1e9;
int dfs_subtree(int node, int prev){
    sub[node] = 1;
    for(auto& edge : adj[node]){
        if(edge.first != prev && !marked[edge.first]){
            sub[node] += dfs_subtree(edge.first, node);
        }
    }
    return sub[node];
}
int find_centroid(int node, int prev){
    for(auto& edge : adj[node]){
        if(edge.first != prev && !marked[edge.first] && 2 * sub[edge.first] > sz){
            return find_centroid(edge.first, node);
        }
    }
    return node;
}
vector<pair<int,int>>weights[N];
vector<pair<int,int>>all;
void dfs(int start, int node, int prev, int cur, int len){
  if(cur>k)return;
  weights[start].push_back({cur,len});
  all.push_back({cur,len});
  for(auto & edge : adj[node]){
    if(edge.first != prev && !marked[edge.first]){
      dfs(start, edge.first, node, cur + edge.second, len + 1);
    }
  }
}
void decompose(int node){
  dfs_subtree(node, -1);
  sz = sub[node];
  int c = find_centroid(node, -1);
  all.push_back(make_pair(0,0));
  for(auto& edge : adj[c]){
    if(marked[edge.first])continue;
    dfs(edge.first, edge.first, c, edge.second, 1);
  }
  for(auto& edge : adj[c]){
    if(marked[edge.first])continue;
    int child = edge.first;
    for(auto& p : weights[child]){
      int d = k - p.first;
      // child either doesnt have d or has (d, l), (d, l + 1), ..., (d, r)
      auto l = lower_bound(weights[child].begin(), weights[child].end(), make_pair(d,0));
      if(l == weights[child].end() || l->first != d){//child doesnt have d
        auto it = lower_bound(all.begin(),all.end(),make_pair(d,0));
        if(it != all.end() && it->first == d){
          ans = min(ans, p.second + it->second);
        }
      }else{
        auto r = upper_bound(weights[child].begin(), weights[child].end(), make_pair(d, (int)1e9)) - 1;
        auto it = lower_bound(all.begin(), all.end(), make_pair(d,0));
        if(it->second >= l->second){
          it = upper_bound(all.begin(),all.end(),make_pair(r->first, r->second));
          if(it != all.end() && it->first == d){
            ans = min(ans, p.second + it->second);
          }
        }else{
          ans = min(ans, p.second + it->second);
        }
      }
    }
  }
  marked[c] = 1;
  all.clear();
  all.shrink_to_fit();
  for(auto& edge : adj[c]){
    int child = edge.first;
    if(!marked[child]){
      weights[child].clear();
      weights[child].shrink_to_fit();
      //decompose(child);
    }
  }
  for(auto&edge:adj[c]){
    if(!marked[edge.first])decompose(edge.first);
  }
}
int best_path(int N, int K, int H[][2], int L[])
{
  k=K;
  for(int i = 0; i < N - 1; i++){
    adj[H[i][0]].push_back({H[i][1],L[i]});
    adj[H[i][1]].push_back({H[i][0],L[i]});
  }
  decompose(0);
  return ans;
}

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