제출 #1270867

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1270867		andrezitos	경주 (Race) (IOI11_race)	C++20	0 / 100	0 ms	328 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long int
#define INF LONG_LONG_MAX/2

int flagAtual=1;

vector<pair<int, ll>> melhor;
vector<bool> block;
vector<pair<int, ll>> edges_dist;

// Respota.
ll menor_K = INF;

//calcula o tamanho da subarvore
void get_SubTreeSize( vector<vector<pair<int, ll>>>  &adj, vector<int> &subtreeSz, int v, int pai) {
  subtreeSz[v] = 1;
  for(auto& [u, val] : adj[v]) {
    if(u == pai || block[u]) continue;
    get_SubTreeSize(adj,subtreeSz,u,v);
    subtreeSz[v] += subtreeSz[u];
  }
}

//percorre todos os vertices  e retorna o centroide...
int findCentroid(vector<vector<pair<int, ll>>> &adj, vector<int> &subtreeSz, int v, int pai, int size) {
  bool isCentroid = true;
  for(auto& [u, val] : adj[v]) {
    if(u == pai) isCentroid &= (size - subtreeSz[v]) <= size/2;
    else isCentroid &= (subtreeSz[u] <= size/2);
  }

  if(isCentroid) return v;
  for(auto& [u, val] : adj[v]) {
    if(u == pai) continue;
    if(subtreeSz[u] > size/2) 
        return findCentroid(adj,subtreeSz,u,v, size);
   }

   return -1;
}


void dfs1(vector<vector<pair<int, ll>>>&adj, int v, int pai, long long int dist, int total, int K) {
  if(dist > K) return;
  edges_dist[v] = {total, dist};

  ll aux = melhor[K-dist].second == flagAtual? melhor[K-dist].first : INF;

  if(aux + total < menor_K)
    menor_K = melhor[K-dist].first + total;

  for(auto& [ch, val] : adj[v])
    if(ch != pai && !block[ch])
      dfs1(adj, ch, v, dist + val, total+1, K);
}

void dfs2(vector<vector<pair<int, ll>>>&adj, int v, int pai, int K) {
  int edges = edges_dist[v].first;
  ll  dist = edges_dist[v].second;
  if(dist > K) return;

  if(melhor[dist].second != flagAtual || melhor[dist].first > edges) {
    melhor[dist].first = edges;
    melhor[dist].second = flagAtual;
  }

	for (auto& [ch, val] : adj[v]) 
    if(!block[ch] && ch != pai) 
      dfs2(adj, ch, v, K);
}

int best_path(int N, int K, int H[][2], int L[]) {
  vector<vector<pair<int, ll>>> adj(N); 
  vector<int> subtreeSz(N);    

  melhor.resize(K+10, {INF, 0});
  block.resize(N, false);
  edges_dist.resize(N);
  
  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]});
  }

  queue<int> Q; Q.push(0);
  while(!Q.empty()) {

    int node = Q.front();
    Q.pop(); block[node] = true;
    
    melhor[0] = {0, flagAtual};

    get_SubTreeSize(adj, subtreeSz, node, -1);

    for(auto& [ch, val] : adj[node])
      if(!block[ch]) {
        dfs1(adj, ch, node, val, 1, K);
        dfs2(adj, ch, node, K);
        Q.push(findCentroid(adj, subtreeSz, ch, node, subtreeSz[ch]));
      }

    flagAtual++;
  }

  if(menor_K == INF) menor_K = -1;
  return menor_K;
}

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