답안 #1087320

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1087320	2024-09-12T13:33:03 Z	quangminh412	경주 (Race) (IOI11_race)	C++14	컴파일 오류	0 ms	0 KB

race

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

/*
  John Watson
  https://codeforces.com/profile/quangminh98

  Mua Code nhu mua Florentino !!
*/

#define faster() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long

const int oo = 1e9;
const int maxn = 2e5 + 9;

vector<pair<int, int>> adj[maxn];
int del[maxn], sz[maxn], h[maxn];
vector<int> cnt;
int n, k, res = oo;

int subtree(int u, int p = -1)
{
  sz[u] = 1;
  for (pair<int, int> nxt : adj[u])
  {
    int v = nxt.first;
    if (v == p || del[v]) continue;
    
    sz[u] += subtree(v, u);
  }
  return sz[u];
}

int find_centroid(int u, int p, int N)
{
  for (pair<int, int> nxt : adj[u])
  {
    int v = nxt.first;
    if (v == p || del[v]) continue;
    
    if (sz[v] > N / 2)
      return find_centroid(v, u, N);
  }
  return u;
}

void count(int u, int p, int w, int h)
{
	if (w > k) return;
	if (cnt[k - w] != oo)
		res = min(res, cnt[k - w] + h);
		
	for (pair<int, int> nxt : adj[u])
	{
		int v = nxt.first;
		if (del[v] || v == p) continue;
		
		count(v, u, w + nxt.second, h + 1);
	}
}

void update(int u, int p, int w, int h)
{
	if (w > k) return;
	cnt[w] = min(cnt[w], h);
	
	for (pair<int, int> nxt : adj[u])
	{
		int v = nxt.first;
		if (del[v] || v == p) continue;
		
		update(v, u, w + nxt.second, h + 1);
	}
}

void centroid_decomposition(int u)
{
	int centroid = find_centroid(u, -1, subtree(u));
	del[centroid] = 1;
	
	for (int i = 1; i <= k; i++) cnt[i] = oo;
	
	for (pair<int, int> nxt : adj[centroid])
	{
		int v = nxt.first;
		if (del[v]) continue;
		
		count(v, centroid, nxt.second, 1);
		update(v, centroid, nxt.second, 1);
	}
	
	for (pair<int, int> nxt : adj[centroid])
	{
		int v = nxt.first;
		if (del[v]) continue;
		
		centroid_decomposition(v);
	}
}

int best_path(int _n, int _k, int H[][2], int l[]) 
{
	n = _n;
	k = _k;
	cnt.resize(k + 5, oo);
	cnt[0] = 0;
	for (int i = 0; i < n - 1; i++)
	{
	  int w = l[i];
	  int u = H[i][0], v = H[i][1];
	  adj[u].push_back({v, w});
	  adj[v].push_back({u, w});
	}
	
	centroid_decomposition(1);
	
	return (res == oo ? -1 : res);
}

int main()
{
  int n, k; cin >> n >> k;
  int h[n][2];
  for (int i = 0; i < n - 1; i++)
    cin >> h[i][0] >> h[i][1]; 
  int l[n];
  for (int i = 0; i < n - 1; i++)
    cin >> l[i];
  
  cout << best_path(n, k, h, l);
  
  return 0;
}

Compilation message

/usr/bin/ld: /tmp/cccL0NZH.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccKM8C8E.o:grader.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status