Submission #298027

#	Time	Username	Problem	Language	Result	Execution time	Memory
298027		miss_robot	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KiB

race

#include "grader.h"
#include <bits/stdc++.h>

#pragma GCC optimize("O3")
#define int long long

using namespace std;

int INF = numeric_limits<int>::max()/4, best[1000001];

void dfs(int u, int p, vector<int>& st, vector<int>& active, vector< vector<pair<int, int> > >& g){
	st[u] = 1;
	for(auto &t : g[u]){
		if(!active[t.first] || t.first == p) continue;
		dfs(t.first, u, st, active, g);
		st[u] += st[t.first];
	}
}

int fnd(int u, int p, int n, vector<int>& st, vector<int>& active, vector< vector<pair<int, int> > >& g){
	for(auto &t : g[u]){
		if(!active[t.first] || t.first == p) continue;
		if(st[t.first] > n/2) return fnd(t.first, u, n, st, active, g);
	}
	return u;
}

void sum(int u, int p, int d, int num, vector< pair<int, int> >& temp, vector<int>& active, vector< vector< pair<int, int> > >& g){
	temp.push_back({num++, d});
	for(auto& t : g[u]){
		if(t.first == p || !active[t.first]) continue;
		sum(t.first, u, d+t.second, num, temp, active, g);
	}
}

void solve(int u, int k, vector<int>& st, vector<int>& active, vector< vector< pair<int, int> > >& g, int& b){
	dfs(u, u, st, active, g);
	u = fnd(u, u, st[u], st, active, g);
	vector<int> ers;
	vector< pair<int, int> > temp;
	for(auto &t : g[u]){
		if(!active[t.first]) continue;
		temp.clear();
		sum(t.first, u, t.second, 1, temp, active, g);
		for(auto &q : temp){
			if(q.second > k) continue;
			else b = min(b, q.first + best[k-q.second]);
		}
		for(auto &q : temp) if(q.second <= k) best[q.second] = min(best[q.second], q.first), ers.push_back(q.second);
	}
	for(int &x : ers) best[x] = INF;
	active[u] = 0;
	for(int i = 0; i < (int)g[u].size(); i++)
		if(active[g[u][i].first] && st[g[u][i].first] > 1)
			solve(g[u][i].first, k, st, active, g, b);
}

signed best_path(signed N, signed K, signed H[][2], signed L[]){
	int n = N, k = K, b = INF, u, v, w;
	vector< vector< pair<int, int> > > g(n);
	for(int i = 1; i < n; i++){
		u = H[i-1][0], v = H[i-1][1], w = L[i-1];
		g[u].push_back({v, w}), g[v].push_back({u, w});
	}
	for(int i = 1; i <= k; i++) best[i] = INF;
	vector<int> active(n, 1), st(n);
	solve(0, k, st, active, g, b);
	return (b==INF?-1:b);
}

Compilation message (stderr)

race.cpp:1:10: fatal error: grader.h: No such file or directory
    1 | #include "grader.h"
      |          ^~~~~~~~~~
compilation terminated.