Submission #639984

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

race

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

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
typedef pair<ll,ll> pll;
typedef ld COMPTYPE;
//typedef complex<COMPTYPE> point;
 
#define IOS cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
#define FILEIOS(fn) freopen(fn".in", "r", stdin); freopen(fn".out", "w", stdout);
#define PI 3.14159265358979323846264338327950288419716939937510
#define xx real()
#define yy imag()
#define ff first
#define ss second
#define nl "\n"
#define bl " "
#define pb push_back

template<typename T>
bool chmax(T& val, T nval) { if(val < nval) {val=nval; return true;} return false;}
template<typename T>
bool chmin(T& val, T nval) { if(val > nval) {val=nval; return true;} return false;}

void DEBUGOUT() { cerr << '\n'; }
template<typename Head, typename... Tail>
void DEBUGOUT(Head H, Tail... T) { cerr << ' ' << H; DEBUGOUT(T...); }
#define DEBUG(...) cerr << "(" << #__VA_ARGS__ << "):";  DEBUGOUT(__VA_ARGS__)

void WRITEIN() { return; }
template<typename Head, typename... Tail>
void WRITEIN(Head& H, Tail&... T) { cin >> H; WRITEIN(T...); }
#define win(...) WRITEIN(__VA_ARGS__);

void WRITEOUT() { return; }
template<typename Head, typename... Tail>
void WRITEOUT(Head&& H, Tail&&... T) { cout << H; WRITEOUT(T...); }
#define wout(...) WRITEOUT(__VA_ARGS__);

const int N = 2e5+1;
const int INF = N*2;

int sz[N];
vector<pli> g[N];
vector<pli> vec[N];

int ans=INF;
int n;
ll k;

void dfs_sz(int v, int p) {
	sz[v] = 1;
	for(auto& [c,u] : g[v]) {
		if(p == u) continue;
		dfs_sz(u,v);
		sz[v] += sz[u];
	}
}

void dfs_hld(int v, int p, int keep) {
	int nextu=-1,maxsz=-1;
	ll nextc;

	for(auto& [c,u] : g[v]) {
		if(u == p) continue;
		if(maxsz < sz[u]) {
			maxsz = sz[u];
			nextu = u;
			nextc = c;
		}
	}

	for(auto& [c,u] : g[v]) {
		if(u == p || u == nextu) continue;
		dfs_hld(u,v,0);
	}

	if(nextu != -1) {
		dfs_hld(nextu,v,1);
		swap(vec[nextu], vec[v]); 
		for(auto& [c,sz] : vec[v]) {
			sz++;
			c += nextc;
			if(c==k) chmin(ans,sz);
		}
	}

	for(auto& [c,u] : g[v]) {
		if(u == p || u == nextu) continue;
		for(auto& [cc,sz] : vec[u]) {
			if(cc+c > k || sz+1 >= ans) continue;
			vec[v].pb({cc+c,sz+1});
			if(cc+nextc==k) chmin(ans,sz+1);
		}
	}

	vec[v].pb({0ll,0});

	/*
	DEBUG(v);
	for(auto& [c,sz] : g[v]) {
		DEBUG(c,sz);
	}
	*/
}

int32_t main() {
	IOS;

	int v,u;
	ll c;
	win(n,k);

	for(int i = 1; i < n; i++) {
		win(v,u,c);
		g[v].pb({c,u});
		g[u].pb({c,v});
	}

	dfs_sz(0,0);
	dfs_hld(0,0,1);

	if(ans == INF) ans=-1;
	wout(ans,nl);
}

Compilation message (stderr)

race.cpp: In function 'void dfs_hld(int, int, int)':
race.cpp:97:9: warning: 'nextc' may be used uninitialized in this function [-Wmaybe-uninitialized]
   97 |    if(cc+nextc==k) chmin(ans,sz+1);
      |       ~~^~~~~~
/usr/bin/ld: /tmp/ccOopBEh.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc8fQDfi.o:grader.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc8fQDfi.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