Submission #941957

#	Time	Username	Problem	Language	Result	Execution time	Memory
941957		4QT0R	Race (IOI11_race)	C++17	21 / 100	3008 ms	45012 KiB

race

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

vector<pair<int,int>> graph[200004];
bool usun[200004];
int siz[200004];
int ans=200004;
unordered_map<int,int> mp;
int dlugosc;

void prep(int v, int p){
	siz[v]=1;
	for (auto u : graph[v]){
		if (u.first==p || usun[u.first])continue;
		prep(u.first,v);
		siz[v]+=siz[u.first];
	}
}

int find_centr(int v, int p, int n){
	int mx_pod=0,mx_son;
	for (auto u : graph[v]){
		if (u.first==p || usun[u.first])continue;
		if (mx_pod<siz[u.first]){
			mx_son=u.first;
			mx_pod=siz[u.first];
		};
	}
	if (mx_pod*2>n)return find_centr(mx_son,v,n);
	else return v;
}

void dfs1(int v, int p, int odl, int dist){
	if (mp.find(dlugosc-odl)!=mp.end())ans=min(ans,mp[dlugosc-odl]+dist);
	for (auto u : graph[v]){
		if (u.first==p || usun[u.first])continue;
		dfs1(u.first,v,odl+u.second,dist+1);
	}
}

void dfs2(int v, int p, int odl, int dist){
	for (auto u : graph[v]){
		if (u.first==p || usun[u.first])continue;
		dfs2(u.first,v,odl+u.second,dist+1);
	}
	if (mp.find(odl)==mp.end())mp[odl]=dist;
	else mp[odl]=min(mp[odl],dist);
}

void dekomp(int v){
	prep(v,-1);
	int centr=find_centr(v,-1,siz[v]);
	usun[centr]=true;
	mp.clear();
	for (auto u : graph[centr]){
		if (usun[u.first])continue;
		dfs1(u.first,centr,u.second,1);
		dfs2(u.first,centr,u.second,1);
	}
	if (mp.find(dlugosc)!=mp.end())ans=min(ans,mp[dlugosc]);
	for (auto u : graph[centr]){
		if (usun[u.first])continue;
		dekomp(u.first);
	}
}

int best_path(int n, int k, int h[][2], int l[]){
	dlugosc=k;
	for (int i = 0; i<n-1; i++){
		graph[h[i][0]].push_back({h[i][1],l[i]});
		graph[h[i][1]].push_back({h[i][0],l[i]});
	}
	dekomp(0);
	if (ans>200000)return -1;
	return ans;
}

Compilation message (stderr)

race.cpp: In function 'int find_centr(int, int, int)':
race.cpp:21:15: warning: 'mx_son' may be used uninitialized in this function [-Wmaybe-uninitialized]
   21 |  int mx_pod=0,mx_son;
      |               ^~~~~~
race.cpp: In function 'void dekomp(int)':
race.cpp:58:7: warning: 'mx_son' may be used uninitialized in this function [-Wmaybe-uninitialized]
   58 |   dfs2(u.first,centr,u.second,1);
      |   ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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