Submission #915818

#	Time	Username	Problem	Language	Result	Execution time	Memory
915818		Julto	Race (IOI11_race)	C++14	0 / 100	3 ms	14684 KiB

race

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

const int mxN = 2e5 + 5, inf = 1e9;

int sz[mxN], cenPar[mxN], dep[mxN], par[mxN][18], sum[mxN];
vector<array<int, 2>> adj[mxN];
vector<array<int, 4>> dists[mxN];
bool done[mxN];

void dfs(int u, int p){
		par[u][0] = p;
		for(int i = 1; i < 18; i++){
				par[u][i] = par[par[u][i - 1]][i - 1];
		}
		for(auto i : adj[u]){
				if(i[0] == p) continue;
				dep[i[0]] = dep[u] + 1;
				sum[i[0]] = sum[u] + i[1];
				dfs(i[0], u);
		}
}

int lca(int a, int b){
		if(dep[a] < dep[b]){
				swap(a, b);
		}
		for(int i = 17; i >= 0; i--){
				if(dep[a] - (1 << i) >= dep[b]){
						a = par[a][i];
				}
		}
		if(a == b){
				return a;
		}
		for(int i = 17; i >= 0; i--){
				if(par[a][i] != par[b][i]){
						a = par[a][i];
						b = par[b][i];
				}
		}
		return par[a][0];
}

int calcDist(int a, int b){
		return sum[a] + sum[b] - 2 * sum[lca(a, b)];
}

int calcEdge(int a, int b){
	return dep[a] + dep[b] - 2 * dep[lca(a, b)];
}

int calcSz(int u, int p){
		sz[u] = 1;
		for(auto i : adj[u]){
				if(i[0] == p || done[i[0]]) continue;
				sz[u] += calcSz(i[0], u);
		}
		return sz[u];
}

int get(int u, int p, int x){
		for(auto i : adj[u]){
				if(i[0] == p || done[i[0]]) continue;
				if(sz[i[0]] * 2 > x){
						return get(i[0], u, x);
				}
		}
		return u;
}

int build(int u){
		int centroid = get(u, u, calcSz(u, u));
		done[centroid] = 1;
		dists[centroid].push_back({0, centroid, centroid});
		for(auto i : adj[centroid]){
				if(!done[i[0]]){
						int x = build(i[0]);
						cenPar[x] = centroid;
						for(auto j : dists[x]){
								dists[centroid].push_back({calcDist(centroid, j[2]), calcEdge(centroid, j[2]), x, j[2]});
						}
				}
		}
		sort(dists[centroid].begin(), dists[centroid].end());
		return centroid;
}

int qry(int v, int k){
		int cur = v, subtree = v;
		int ans = inf;
		while(cur != -1){
				int goal = k - calcDist(v, cur);
				array<int, 4> find = {goal, -inf, -inf, -inf};
				int lb = lower_bound(dists[cur].begin(), dists[cur].end(), find) - dists[cur].begin();
				for(int j = lb; j < dists[cur].size() && dists[cur][j][0] == goal; j++){
						if(dists[cur][j][2] == subtree) continue;
	          int x = calcEdge(cur, v);
						ans = min(ans, x + dists[cur][j][1]);
					  cout << v << " " << dists[cur][j][2] << ' ' << x + dists[cur][j][1] << '\n';
					  break;
						
				}
				subtree = cur;
				cur = cenPar[cur];

		}
		return ans;
}

int best_path(int n, int k, int h[][2], int l[]){
		for(int i = 0; i < n - 1; i++){
				adj[h[i][0]].push_back({h[i][1], l[i]});
				adj[h[i][1]].push_back({h[i][0], l[i]});
		}
		dfs(0, 0);
		for(int i = 0; i < n; i++){
				cenPar[i] = -1;
		}
		build(0);
		/*for(int i = 0; i < n; i++){
				cout << cenPar[i] << " ";
		}
		cout << '\n';
		for(int i = 0; i < n; i++){
				cout << i << '\n';
				for(auto j : dists[i]){
						cout << j[0] << " " << j[1] << " " << j[2] << "\n";
				}
				cout << '\n';
		}*/
		int ans = inf;
		for(int i = 0; i < n; i++){
				//cout << qry(i, k) << " ";
				ans = min(ans, qry(i, k));
		}

		return (ans == inf ? -1 : ans);
}

Compilation message (stderr)

race.cpp: In function 'int qry(int, int)':
race.cpp:96:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 4> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     for(int j = lb; j < dists[cur].size() && dists[cur][j][0] == goal; j++){
      |                     ~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57