Submission #1102538

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1102538	2024-10-18T08:53:38 Z	seoul_korea	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KB

race

#include <bits/stdc++.h>

using namespace std;

const bool multiTest = 0;
#define TASK ""
#define REP(i, n) for(int i = 1; i <= n; i++)
#define FOR(i, a, b) for(auto i = a; i <= b; i++)
#define FORD(i, a, b) for(auto i = a; i >= b; i--)
template<class T> bool maximize(T& a, T b) { if(a < b) return a = b, 1; return 0; }
template<class T> bool minimize(T& a, T b) { if(a > b) return a = b, 1; return 0; }

mt19937 rng(time(0));

const int maxN = (int)2e5 + 7, maxK = (int)1e6 + 7, INF = (int)1e9 + 7;
using ii = pair<int, int>;
int f[maxK], child[maxN];
bool del[maxN];
vector<ii> G[maxN];
vector<int> used;
int numNode, limK;

int getSize(int u, int p = -1) {
	child[u] = 1;
	for(ii nxt : G[u]) {
		int v = nxt.first, w = nxt.second;
		if(v == p || del[v]) continue;
		child[u] += getSize(v, u);
	}
	return child[u];
}

int getCentroid(int sz, int u, int p = -1) {
	for(ii nxt : G[u]) {
		int v = nxt.first;
		if(!del[v] && v != p && child[v] > sz) return getCentroid(sz, v, u);
	}
	return u;
}

int ans = INF;

void calc(int u, bool filling, int dist, int cntEdge, int p = -1) {
	if(dist > limK) return;
	if(filling) {
		minimize(f[dist], cntEdge);
		used.push_back(dist);
	}
	else minimize(ans, f[limK - dist] + cntEdge);
	for(ii nxt : G[u]) {
		int v = nxt.first, w = nxt.second;
		if(del[v] || v == p) continue;
		calc(v, filling, dist + w, cntEdge + 1, u);
	}
}

void dnc(int x = 1) {
	int root = getCentroid(getSize(x) >> 1, x);
	//cout << root << endl;
	del[root] = 1;
 	for(ii nxt : G[root]) {
		int v = nxt.first, w = nxt.second;
		if(del[v]) continue;
		calc(v, 0, w, 1);
		calc(v, 1, w, 1);
	}
	for(int d : used) {
		f[d] = INF;
	}
	used.clear();
	for(ii nxt : G[root]) {
		int v = nxt.first, w = nxt.second;
		if(del[v]) continue;
		dnc(v);
	}
}

void solve(const int& curTest) {
	cerr << "\n>TEST #" << curTest << "<\n";
	// GET AC PLEASE
	cin >> numNode >> limK;
	REP(i, numNode - 1) {
		int u, v, w;
		cin >> u >> v >> w;
		u++; v++;
		G[u].push_back({v, w});
		G[v].push_back({u, w});
	}
	memset(f, 0x3f, sizeof f);
	f[0] = 0;
	dnc();
	if(ans == INF) {
		cout << -1 << endl;
		return;
	}
	cout << ans << endl;
}

signed main() {
	cin.tie(0)->ios_base::sync_with_stdio(0);

	if(fopen("TASK.INP", "r")) freopen("TASK.INP", "r", stdin);
	if(fopen(TASK".INP", "r")) {
			freopen(TASK".INP", "r", stdin);
			freopen(TASK".OUT", "w", stdout);
	}

	int nTest = 1;
	if(multiTest) cin >> nTest;
	for(int iTest = 1; iTest <= nTest; iTest++) solve(iTest);

	return 0;
}

Compilation message

race.cpp: In function 'int getSize(int, int)':
race.cpp:26:22: warning: unused variable 'w' [-Wunused-variable]
   26 |   int v = nxt.first, w = nxt.second;
      |                      ^
race.cpp: In function 'void dnc(int)':
race.cpp:72:22: warning: unused variable 'w' [-Wunused-variable]
   72 |   int v = nxt.first, w = nxt.second;
      |                      ^
race.cpp: In function 'int main()':
race.cpp:102:36: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |  if(fopen("TASK.INP", "r")) freopen("TASK.INP", "r", stdin);
      |                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:104:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |    freopen(TASK".INP", "r", stdin);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:105:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |    freopen(TASK".OUT", "w", stdout);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccXHNfOQ.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc6lPKPP.o:grader.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc6lPKPP.o: in function `main':
grader.cpp:(.text.startup+0x28): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status