Submission #849014

#	Time	Username	Problem	Language	Result	Execution time	Memory
849014		BidoTeima	Race (IOI11_race)	C++17	0 / 100	2 ms	9716 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;
} 
map<int,int>mp{};
vector<pair<int,int>>vc;
void dfs( int node, int prev, int cur, int len){
  if(cur>k)return;
  vc.push_back({cur,len});
  auto it = mp.find(k - cur);
  if(it != mp.end()){
    ans = min(ans, it->second+len);
  } 
  for(auto & edge : adj[node]){
    if(edge.first != prev && !marked[edge.first]){
      dfs(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);
  mp[0]=0;
  for(auto&edge:adj[c]){
    int child = edge.first;
    if(!marked[child]){
      vc.clear();
      dfs(child, c, edge.second, 1);
      for(auto&p:vc){
        auto it = mp.find(p.first);
        if(it==mp.end()){
          mp[p.first]=p.second;
        }else{
          it->second=min(it->second, p.second);
        }
      }
    }
  }
  marked[c] = 1;
  mp.clear();
  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