Submission #172460

#	Time	Username	Problem	Language	Result	Execution time	Memory
172460		cgiosy	경주 (Race) (IOI11_race)	C++17	0 / 100	2 ms	376 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define rep(i,x,n) for(int i=x; i<n; i++)
using namespace std;
constexpr int INF=1e9;

int best_path(int N, int K, int H[][2], int L[]) {
	int m=INF;
	vector<bool> V(N);
	vector<int> C(N, 1), D(K+1, INF), X;
	vector<pair<int, int>> Y;
	vector<vector<pair<int, int>>> G(N);
	rep(i, 1, N) {
		int x=H[i][0], y=H[i][1], z=L[i];
		G[x].push_back({y, z});
		G[y].push_back({x, z});
	}
	#define ITER(i) for(auto[j,w]:G[i]) if(j!=p && !V[j])
	function<void(int, int)> cnt=[&](int i, int p) {
		ITER(i) cnt(j, i), C[i]+=C[j];
	};
	function<int(int, int, int)> cent=[&](int i, int p, int n) {
		ITER(i) if(C[j]>n/2) {
			C[j]+=C[i]-=C[j];
			return cent(j, i, n);
		}
		return i;
	};
	function<void(int, int, int, int)> f=[&](int i, int p, int d, int k) {
		X.push_back(d);
		m=min(m, k+D[K-d]);
		ITER(i) if(d+w<=K && k+1<m) {
			f(j, i, d+w, k+1);
			if(i==p) {
				for(auto[x,y]:Y) D[x]=min(D[x], y);
				Y.clear();
			}
		}
		Y.push_back({d, k});
	};
	function<void(int, int)> cd=[&](int i, int p) {
		V[i=cent(i, p, C[i])]=true, D[0]=0;
		f(i, i, 0, 0);
		for(int x:X) D[x]=INF;
		X.clear();
		ITER(i) cd(j, i);
	};
	cnt(0, 0);
	cd(0, 0);
	return (m==INF?-1:m);
}

Compilation message (stderr)

race.cpp: In lambda function:
race.cpp:18:30: warning: unused variable 'w' [-Wunused-variable]
  #define ITER(i) for(auto[j,w]:G[i]) if(j!=p && !V[j])
                              ^
race.cpp:20:3: note: in expansion of macro 'ITER'
   ITER(i) cnt(j, i), C[i]+=C[j];
   ^~~~
race.cpp: In lambda function:
race.cpp:18:30: warning: unused variable 'w' [-Wunused-variable]
  #define ITER(i) for(auto[j,w]:G[i]) if(j!=p && !V[j])
                              ^
race.cpp:23:3: note: in expansion of macro 'ITER'
   ITER(i) if(C[j]>n/2) {
   ^~~~
race.cpp: In lambda function:
race.cpp:18:30: warning: unused variable 'w' [-Wunused-variable]
  #define ITER(i) for(auto[j,w]:G[i]) if(j!=p && !V[j])
                              ^
race.cpp:46:3: note: in expansion of macro 'ITER'
   ITER(i) cd(j, i);
   ^~~~

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