Submission #1303602

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303602		mdobric	Race (IOI11_race)	C++20	0 / 100	11 ms	19240 KiB

race

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

const int maxn = 200005;
vector <pair <int, int> > v[maxn];
set <pair <int, int> > s[maxn];
set <pair <int, int> > :: iterator it, it2;
map <int, int> m[maxn];
int ans = 1e9, parent[maxn];

int find (int x){
	if (parent[x] == x) return x;
	return parent[x] = find(parent[x]);
}

void unite (int x, int y, int d, int k){
	//cout << "unite " << x << " " << y << " " << d << " " << k << endl;
	if (s[x].size() < s[y].size()) swap(x, y);
	for (it = s[y].begin(); it != s[y].end(); it++){
		int duzina = it -> first;
		duzina += d;
		int vrhovi = it -> second;
		if (m[x][k - duzina] != 0) ans = min(ans, m[x][k - duzina] + vrhovi);
	}
	for (it = s[y].begin(); it != s[y].end(); it++){
		int duzina = it -> first;
		duzina += d;
		int vrhovi = it -> second;
		vrhovi++;
		//cout << duzina << " " << vrhovi << endl;
		it2 = s[x].lower_bound({duzina, 0});
		if (it2 != s[x].end() and it2 -> first == duzina and (it2 -> second) > vrhovi){
			s[x].erase(it2);
			s[x].insert({duzina, vrhovi});
			m[x][duzina] = vrhovi;
		}
		else if ((it2 == s[x].end()) or ((it2 -> first) != duzina)){
			s[x].insert({duzina, vrhovi});
			m[x][duzina] = vrhovi;
		}
	}
	s[y].clear();
	m[y].clear();
}

void dfs (int x, int p, int k){
	for (int i = 0; i < v[x].size(); i++){
		int y = v[x][i].first;
		int d = v[x][i].second;
		if (y != p){
			dfs(y, x, k);
			//cout << "spajam " << x << " " << y << endl;
			int px = find(x);
			int py = find(y);
			unite(px, py, d, k);
		}
	}
}

int best_path (int n, int k, int h[maxn][2], int l[maxn]){
	for (int i = 0; i < n - 1; i++){
		v[h[i][0]].push_back({h[i][1], l[i]});
		v[h[i][1]].push_back({h[i][0], l[i]});
	}
	for (int i = 0; i < n; i++) s[i].insert({0, 1}), m[i][0] = 1, parent[i] = i;
	dfs(0, 0, k);
	if (ans == 1e9) return -1;
	else return ans - 1;
}

/*
int main (void){
	
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, k, h[maxn][2], l[maxn];
	cin >> n >> k;
	for (int i = 0; i < n - 1; i++) cin >> h[i][0] >> h[i][1] >> l[i];
	cout << best_path(n, k, h, l) << endl;

	return 0;
}
*/

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