Submission #886411

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

race

/**
 *    author:  AgentPengin ( Độc cô cầu bại )
 *    created: 23.12.2022 10:08:02
 *    too lazy to update time
**/
#define EL '\n'
#define fi first
#define se second
#define NAME "TASK"
#define ll long long
#define lcm(a,b) (a/gcd(a,b))*b
#define db(val) "["#val" = " << (val) << "] "
#define bend(v) (v).begin(),(v).end()
#define sz(v) (int)(v).size()
#define ex exit(0)
#define int ll
 
using namespace std;
 
const ll mod = 1e9 + 7;
const int inf = 0x1FFFFFFF;
const int MAXN = 2e5 + 5;
const int MAXC = 1e6 + 5;

int n,k,sz[MAXN],ans = inf;
vector<pair<int,int>> adj[MAXN];
bool deleted[MAXN];
 
int get_subtree_sizes(int u,int p = 0) {
	sz[u] = 1;
	for (auto v : adj[u]) {
		if (!deleted[v.fi] && v.fi != p) {
			sz[u] += get_subtree_sizes(v.fi,u);	
		}
	}
	return sz[u];
}
 
int find_centroid(int desired,int u,int p = 0) {
	for (auto v : adj[u]) {
		if (v.fi != p && !deleted[v.fi] && sz[v.fi] >= desired) {
			return find_centroid(desired,v.fi,u);
		}
	}
	return u;
}
 
unordered_map<int,int> mp;
vector<pair<int,int>> update;
int mx_len,cnt[MAXC];
 
void dfs(int u,int p,int len,int depth) {
	if (len > k) return;
	if (cnt[k - len] != -1) {
		ans = min(ans,cnt[k - len] + depth);
	}
	mx_len = max(mx_len,len);
	update.emplace_back(len,depth);
	for (auto v : adj[u]) {
		if (v.fi != p && !deleted[v.fi]) {
			dfs(v.fi,u,len + v.se,depth + 1);
		}
	}
}
 
void solve(int u) {
	int centroid = find_centroid(get_subtree_sizes(u) >> 1,u);	
	cnt[0] = 0;
	mx_len = 0;
	for (auto v : adj[centroid]) {
		if (deleted[v.fi]) continue;
		// solve for v
		dfs(v.fi,centroid,v.se,1);
		for (auto x : update) {
			if (cnt[x.fi] == -1) cnt[x.fi] = x.se;
			else cnt[x.fi] = min(cnt[x.fi],x.se);
		}
		// update for v
		update.clear();
	}
	fill(cnt,cnt + mx_len + 1,-1);
	deleted[centroid] = true;
	for (auto v : adj[centroid]) {
		if (!deleted[v.fi]) {
			solve(v.fi);
		}
	}
}

int best_path(int N, int K, int H[][2], int L[]) {
	n = N,k = K;
	for (int i = 0;i < n - 1;i++) {
		adj[H[i][0] + 1].emplace_back(H[i][1] + 1,L[i]);
		adj[H[i][1] + 1].emplace_back(H[i][0] + 1,L[i]);
	}
	solve(1);
	if (ans > n) return -1;
	else return ans;
}
// agent pengin wants to take apio (with anya-san)

Compilation message (stderr)

race.cpp:26:1: error: 'vector' does not name a type
   26 | vector<pair<int,int>> adj[MAXN];
      | ^~~~~~
race.cpp: In function 'long long int get_subtree_sizes(long long int, long long int)':
race.cpp:31:16: error: 'adj' was not declared in this scope
   31 |  for (auto v : adj[u]) {
      |                ^~~
race.cpp: In function 'long long int find_centroid(long long int, long long int, long long int)':
race.cpp:40:16: error: 'adj' was not declared in this scope
   40 |  for (auto v : adj[u]) {
      |                ^~~
race.cpp: At global scope:
race.cpp:48:1: error: 'unordered_map' does not name a type
   48 | unordered_map<int,int> mp;
      | ^~~~~~~~~~~~~
race.cpp:49:1: error: 'vector' does not name a type
   49 | vector<pair<int,int>> update;
      | ^~~~~~
race.cpp: In function 'void dfs(long long int, long long int, long long int, long long int)':
race.cpp:55:9: error: 'min' was not declared in this scope
   55 |   ans = min(ans,cnt[k - len] + depth);
      |         ^~~
race.cpp:57:11: error: 'max' was not declared in this scope
   57 |  mx_len = max(mx_len,len);
      |           ^~~
race.cpp:58:2: error: 'update' was not declared in this scope
   58 |  update.emplace_back(len,depth);
      |  ^~~~~~
race.cpp:59:16: error: 'adj' was not declared in this scope
   59 |  for (auto v : adj[u]) {
      |                ^~~
race.cpp: In function 'void solve(long long int)':
race.cpp:70:16: error: 'adj' was not declared in this scope
   70 |  for (auto v : adj[centroid]) {
      |                ^~~
race.cpp:74:17: error: 'update' was not declared in this scope
   74 |   for (auto x : update) {
      |                 ^~~~~~
race.cpp:76:21: error: 'min' was not declared in this scope
   76 |    else cnt[x.fi] = min(cnt[x.fi],x.se);
      |                     ^~~
race.cpp:79:3: error: 'update' was not declared in this scope
   79 |   update.clear();
      |   ^~~~~~
race.cpp:81:2: error: 'fill' was not declared in this scope; did you mean 'fi'?
   81 |  fill(cnt,cnt + mx_len + 1,-1);
      |  ^~~~
      |  fi
race.cpp:83:16: error: 'adj' was not declared in this scope
   83 |  for (auto v : adj[centroid]) {
      |                ^~~
race.cpp: In function 'long long int best_path(long long int, long long int, long long int (*)[2], long long int*)':
race.cpp:93:3: error: 'adj' was not declared in this scope
   93 |   adj[H[i][0] + 1].emplace_back(H[i][1] + 1,L[i]);
      |   ^~~