Submission #676095

#	Time	Username	Problem	Language	Result	Execution time	Memory
676095		esomer	Race (IOI11_race)	C++17	0 / 100	3 ms	5016 KiB

race

#include<bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define endl "\n"
 
const int MOD = 998244353;
const int maxN = 200000;
const int maxK = 1000001;

vector<pair<int, ll>> adj[maxN];
int curr[maxK];
int sub[maxN];
bool done[maxN];
vector<int> changed;
int n, k, ans;

int find_size(int x, int p){
	int sz = 1;
	for(auto pr: adj[x]){
		if(done[pr.first] == 0 && p != pr.first){
			sz += find_size(pr.first, x);
		}
	}
	sub[x] = sz;
	return sz;
}

int get_centroid(int x, int sz, int p){
	for(auto pr : adj[x]){
		if(done[pr.first] == 0 && p != pr.first && sub[pr.first] > sz / 2){
			return get_centroid(pr.first, sz, x);
		}
	}
	return x;
}

void gt(int x, int p, ll km, int edges){
	if(km > k) return;
	int need = k - km;
	if(curr[need] != -1) ans = min(ans, edges + curr[need]);
	for(auto pr : adj[x]){
		if(done[pr.first] == 0 && p != pr.first){
			gt(pr.first, x, km + pr.second, edges + 1);
		}
	}
}

void st(int x, int p, ll km, int edges){
	if(km >= k) return;
	if(curr[km] == -1){
		curr[km] = edges;
		changed.push_back(km);
	}else curr[km] = min(curr[km], edges);
	for(auto pr : adj[x]){
		if(done[pr.first] == 0 && p != pr.first){
			st(pr.first, x, km + pr.second, edges + 1);
		}
	}
}


void decompose(int x){
	int sz = find_size(x, -1);
	int centr = get_centroid(x, sz, -1);
	done[centr] = 1;
	curr[0] = 0; changed.push_back(0);
	for(auto p : adj[centr]){
		if(!done[p.first]){
			gt(p.first, x, p.second, 1);
			st(p.first, x, p.second, 1);
		}
	}
	for(int y : changed) curr[y] = -1;
	changed.clear();
	for(auto p : adj[centr]){
		if(!done[p.first]) {decompose(p.first);}
	}
}

int best_path(int N, int K, int H[][2], int L[]){
	n = N; k = K;
	for(int i = 0; i < N - 1; i++){
		int u = H[i][0]; int v = H[i][1];
		adj[u].push_back({v, L[i]});
		adj[v].push_back({u, L[i]});
	}
	for(int i = 0; i <= k; i++) curr[i] = -1;
	for(int i = 0; i <= n; i++) {done[i] = 0; sub[i] = 0;}
	ans = 1e9;
	decompose(0);
	return (ans == 1e9 ? -1 : ans);
}
 
//~ #define MAX_N 500000
 
//~ static int N, K;
//~ static int H[MAX_N][2];
//~ static int L[MAX_N];
//~ static int solution;

//~ inline 
//~ void my_assert(int e) {if (!e) abort();}

//~ void read_input()
//~ {
  //~ int i;
  //~ my_assert(2==scanf("%d %d",&N,&K));
  //~ for(i=0; i<N-1; i++)
    //~ my_assert(3==scanf("%d %d %d",&H[i][0],&H[i][1],&L[i]));
  //~ my_assert(1==scanf("%d",&solution));
//~ }

//~ int main()
//~ {
  //~ int ans;
  //~ read_input();
  //~ ans = best_path(N,K,H,L);
  //~ if(ans==solution)
    //~ printf("Correct.\n");
  //~ else
    //~ printf("Incorrect. Returned %d, Expected %d.\n",ans,solution);

  //~ return 0;
//~ }

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