Submission #745582

#	Time	Username	Problem	Language	Result	Execution time	Memory
745582		shoryu386	Race (IOI11_race)	C++17	21 / 100	173 ms	54576 KiB

race

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

//#include "race.h"
#define int long long
int n,k;
#define MAXN 200007
unordered_map<int, int> al[MAXN];

int ans = 2*MAXN;

unordered_map<int, int> merger[MAXN];
int offset[MAXN] = {0};
int valoffset[MAXN] = {0};

int dfs(int node, int p){
	
	int largest = -1, largestVal = -1;
	int totalSize = 1;
	for (auto x : al[node]){
		
		if (x.first == p) continue;
		int ss = dfs(x.first, node);
		totalSize += ss;
		if (ss > largestVal){
			largestVal = ss; largest = x.first;
		}
	}
	
	//we need to merge while checking :D
	
	if (largest != -1){
		swap(merger[node], merger[largest]);
		offset[node] = offset[largest] + al[node][largest];
		valoffset[node] = valoffset[largest] + 1;
		
		merger[node][-offset[node]] = -valoffset[node];
		
		if (merger[node].count(k - offset[node]) != 0){
			int torture = merger[node][k - offset[node]];
			ans = min(ans, torture + valoffset[node]);
		}
		
		for (auto x : al[node]){
			if (x.first == p || x.first == largest) continue;
			for (auto y : merger[x.first]){
				//check if x.second + y.first - offset[x.first] can form k with a value from (merger[node]) but offset by offset[node]
				//check if k - (x.second + y.first - offset[x.first] - offset[node]) can be found
				
				int trueValSec = y.first + offset[x.first] + al[node][x.first];
				//cerr << node << ' ' << x.first << ' ' << trueValSec << ' ' << k - trueValSec + offset[node] << '\n';
				
				/*
				cout << "For node " << node << '\n';
				for (auto x : merger[node]){
					if (x.first + offset[node] == k){
						//ans = min(ans, x.second + valoffset[node]);
					}
					cout << x.first + offset[node] << ' ' << x.second + valoffset[node] << '\n';
				}
				* */
				//we want k = trueval + trueValSec
				//k - truevalSec = trueVal
				//k - trueValSec = valFound - offset
				//k - trueValSec + offset[node] = valFound
				//valFound = trueval + offset[]
				
				//if (node == 0 && x.first == 1) cout << trueValSec << ' ' << k - trueValSec - offset[node] << "\n\n\n";
				if (merger[node].count(k - trueValSec - offset[node]) != 0){
					int torture = merger[node][k - trueValSec - offset[node]] + valoffset[x.first];
					
					ans = min(ans, torture + y.second + valoffset[node] + 1);
				}
			}

			for (auto y : merger[x.first]){
				
				int intendedAdd = y.first + offset[x.first] - offset[node] + x.second;
				
				if (merger[node].count(intendedAdd) == 0 || merger[node][intendedAdd] > y.second + 1 - valoffset[x.first] - valoffset[node]){
					merger[node][intendedAdd] = y.second + 1 + valoffset[x.first] - valoffset[node];
				}
			}
		}
	}
	merger[node][-offset[node]] = -valoffset[node];
	
	//cout << "For node " << node << '\n';
	
	if (merger[node].count(k - offset[node]) != 0){
		ans = min(ans, merger[node][k - offset[node]] + valoffset[node]);
	}
	
	/*
	for (auto x : merger[node]){
		if (x.first + offset[node] == k){
			ans = min(ans, x.second + valoffset[node]);
		}
		//cout << x.first + offset[node] << ' ' << x.second + valoffset[node] << '\n';
	}
	*/
	return totalSize;
}

mt19937 mt_rng(chrono::steady_clock::now().time_since_epoch().count());
int randint(int a, int b) {
	return uniform_int_distribution<int>(a, b)(mt_rng);
}

int32_t best_path(int32_t N, int32_t K, int32_t H[][2], int32_t L[]){
	n = N;
	k = K;
	
	for (int x = 0; x < n-1; x++){
		int a, b; a = H[x][0], b = H[x][1];
		al[a][b] = L[x];
		al[b][a] = L[x];
	}
	
	dfs(randint(0, n-1), -1);
	if (ans > MAXN) return -1;
	return ans;
}

/*
main(){
	int32_t H[][2] = {{0,1},{1,2},{1,3}, {0,4},{4,5},{4,6}};
	int32_t L[] = {4,3,2,50,7,9};
	cout << best_path(7, 56, H, L);
}
*/

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