Submission #1111624

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1111624	2024-11-12T11:08:00 Z	TrieTr	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KB

race

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

void local() {
	#define taskname ""
	if(fopen(taskname".inp", "r")) {
		freopen(taskname".inp", "r", stdin);
		freopen(taskname".out", "w", stdout);
	}
}

#define ll long long
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

template <class X, class Y> bool mini(X& x, Y y) {return x > y ? x = y, true : false;}
template <class X, class Y> bool maxi(X& x, Y y) {return x < y ? x = y, true : false;}

typedef pair<int, int> pii;

const int N = 1e6 + 5;

int n, l;
vector<pair<int, int>>adj[N];
bitset<N>del;

int sz[N];
int get_sz(int u, int p = -1) {
	sz[u] = 1;
	for(pii pi : adj[u]) {
		int v, w; tie(v, w) = pi; 
		if(v == p || del[v]) continue;
		sz[u] += get_sz(v, u);
	}
	return sz[u];
}
int find_centroid(int u, int need, int p = -1) {
	for(pii pi : adj[u]) {
		int v, w; tie(v, w) = pi;
		if(v != p && !del[v] && sz[v] > need / 2) return find_centroid(v, need, u);
	}
	return u; 
}
int res = 1e9;
int path[N];
void dfs(int u, int p, int d, int we, int filling) {
	if(we > l) return;
	if(filling == 0) mini(res, d + path[l - we]);
	if(filling == 1) mini(path[we], d);
	if(filling == 2) path[we] = 1e9;
	for(pii pi : adj[u]) {
		int v, w; tie(v, w) = pi;
		if(v != p && !del[v]) dfs(v, u, d + 1, we + w, filling);
	}

}
void decompose(int u) {
	u = find_centroid(u, get_sz(u));
	path[0] = 0; del[u] = true;
	for(pii pi : adj[u]) {
		int v, w; tie(v, w) = pi;
		if(!del[v]) {
			dfs(v, u, 1, w, 0);
			dfs(v, u, 1, w, 1);
		}
	}
	for(pii pi : adj[u]) {
		int v, w; tie(v, w) = pi;
		if(!del[v]) dfs(v, u, 1, w, 2);
	}
	for(pii pi : adj[u]) {
		int v, w; tie(v, w) = pi;
		if(!del[v]) decompose(v);
	}
}

int main() {
	fastio; local();
	cin >> n >> l;
	for(int i = 1; i < n; i++) {
		int u, v, w; cin >> u >> v >> w; u++; v++;
		adj[u].emplace_back(v, w); adj[v].emplace_back(u, w);
	}
	for(int i = 1; i <= l; i++) path[i] = 1e9;
	decompose(1);
	cout << (res >= 1e9 ? -1 : res);
}

Compilation message

race.cpp: In function 'void local()':
race.cpp:7:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |   freopen(taskname".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:8:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |   freopen(taskname".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccTHUPvE.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccUCkCEF.o:grader.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccUCkCEF.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