Submission #1270824

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270824		andrezitos	Race (IOI11_race)	C++20	0 / 100	1 ms	320 KiB

race

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

#define INF INT_MAX/2

int flagAtual=1;

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

//calcula o tamanho da subarvore
void get_SubTreeSize( vector<vector<pair<int, int>>>  &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, int>>> &adj, vector<int> &subtreeSz, int v, int pai, int size) {
	for (auto &[chi, val] : adj[v]) 
		if (chi != pai && !block[chi] && subtreeSz[chi] * 2 > size) 
        return findCentroid(adj, subtreeSz, chi, v, size);
	return v;
}

void dfs1(vector<vector<pair<int, int>>>&adj, int v, int pai, int dist, int total) {
  if(dist >= melhor.size()) return;
  melhor[dist].first = melhor[dist].second < flagAtual? total : min(total, melhor[dist].first);
  melhor[dist].second = flagAtual;
	for (auto& [ch, val] : adj[v]) 
    if(!block[ch] && ch != pai) dfs1(adj, ch, v, dist + val, total+1);
}

void dfs2(vector<vector<pair<int, int>>>&adj, int v, int pai, int dist, int total, int K) {
  if(dist >= melhor.size() || dist >= K) return;
  if(melhor[K-dist].second == flagAtual) {
    melhor[K].first = melhor[K].second < flagAtual? melhor[dist].first + melhor[K-dist].first : min(melhor[dist].first + melhor[K-dist].first, melhor[K].first);
    melhor[K].second = flagAtual;
  }

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

int best_path(int N, int K, int H[][2], int L[]) {
  vector<vector<pair<int, int>>> adj(N); vector<int> subtreeSz(N);
  melhor.resize(K+1, {INF, 0});
  block.resize(N, false);
  int menor_K = INF;
  
  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]});
  }
  
  get_SubTreeSize(adj, subtreeSz, 0, -1);

  queue<int> Q;
  Q.push(findCentroid(adj, subtreeSz, 0, -1, N));

  while(!Q.empty()) {
    int node = Q.front();
    Q.pop();
    
    dfs1(adj, node, -1, 0, 0);
    dfs2(adj, node, -1, 0, 0, K);

    menor_K = melhor[K].second < flagAtual? menor_K : min(menor_K, melhor[K].first);

    get_SubTreeSize(adj, subtreeSz, node, -1);
    for(auto& [ch, val] : adj[node])
      if(!block[ch]) Q.push(findCentroid(adj, subtreeSz, ch, node, subtreeSz[ch]));

    flagAtual++;
    block[node] = true;
  }

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

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