Submission #384487

#	Time	Username	Problem	Language	Result	Execution time	Memory
384487		dongliu0426	Race (IOI11_race)	C++17	Compilation error	0 ms	0 KiB

race

#include <bits/stdc++.h>
using namespace std;
 
const int N = 200001;
const int K = 1000010;
const int inf = 0x3f3f3f3f;

struct L {
	int x, w;
	L *next;
} *aa[N];
 
void link(int i, int j, int k) {
	L *l = new L();
	l->x = j, l->w = k;
	l->next = aa[i];
	aa[i] = l;
};
 
int n, k, ss[N], dep, cc[K];
bool vv[N];
int ans = inf;
 
int subtree(int x, int p = 0) {
	ss[x] = 1;
	for (L *y = aa[x]; y; y = y->next)
		if (!vv[y->x] && y->x != p)
			ss[x] += subtree(y->x, x);
	return ss[x];
}
 
int centroid(int dd, int x, int p = 0) {
	for (L *y = aa[x]; y; y = y->next)
		if (!vv[y->x] && y->x != p && ss[y->x] >= dd)
			return centroid(dd, y->x, x);
	return x;
}
 
void _count(int x, int p, int d, int dd) {
	if (d > k) return;
	dep = max(dep, d);
	ans = min(ans, cc[k - d] + dd);
	for (L *y = aa[x]; y; y = y->next)
		if (!vv[y->x] && y->x != p)
			_count(y->x, x, d + y->w, dd + 1);
}
 
void _fill(int x, int p, int d, int dd) {
	if (d > k) return;
	cc[d] = min(cc[d], dd);
	for (L *y = aa[x]; y; y = y->next)
		if (!vv[y->x] && y->x != p)
			_fill(y->x, x, d + y->w, dd + 1);
}
 
void decomp(int x = 1) {
	int c = centroid(subtree(x) / 2, x);
	vv[c] = 1;
	dep = 0;
	for (L *y = aa[c]; y; y = y->next)
		if (!vv[y->x]) {
			_count(y->x, c, y->w, 1);
			_fill(y->x, c, y->w, 1);
		}
	for (int i = 1; i <= dep; ++i)
		cc[i] = inf;
	for (L *y = aa[c]; y; y = y->next)
		if (!vv[y->x])
			decomp(y->x);
}
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
	scanf("%d%d", &n, &k);
	for (int i = 1, x, y, z; i < n; ++i) {
		scanf("%d%d%d", &x, &y, &z); ++x, ++y;
		link(x, y, z), link(y, x, z);
	}
	memset(cc, 0x3f, sizeof(cc)); cc[0] = 0;
	decomp();
	printf("%d\n", (ans == inf ? -1 : ans));
}

Compilation message (stderr)

race.cpp: In function 'int main()':
race.cpp:74:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   74 |  scanf("%d%d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~
race.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   76 |   scanf("%d%d%d", &x, &y, &z); ++x, ++y;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
/tmp/ccX5v0K1.o: In function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/cc0hsZSq.o:grader.cpp:(.text.startup+0x0): first defined here
/tmp/cc0hsZSq.o: In function `main':
grader.cpp:(.text.startup+0x24): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status