Submission #269756

#	Time	Username	Problem	Language	Result	Execution time	Memory
269756		anubhavdhar	Race (IOI11_race)	C++14	0 / 100	5 ms	5120 KiB

race

#include<bits/stdc++.h>

#include "race.h"

#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first 
#define ss second
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define FOR(i,N) for(i=0;i<(N);++i)
#define FORe(i,N) for(i=1;i<=(N);++i)
#define FORr(i,a,b) for(i=(a);i<(b);++i)
#define FORrev(i,N) for(i=(N);i>=0;--i)
#define F0R(i,N) for(int i=0;i<(N);++i)
#define F0Re(i,N) for(int i=1;i<=(N);++i)
#define F0Rr(i,a,b) for(ll i=(a);i<(b);++i)
#define F0Rrev(i,N) for(int i=(N);i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define dbgLine cerr<<" LINE : "<<__LINE__<<"\n"
#define ldd long double

using namespace std;
/*
const int Alp = 26;
const int __PRECISION = 9;
const int inf = 1e9 + 8;

const ldd PI = acos(-1);
const ldd EPS = 1e-7;

const ll MOD = 1e9 + 7;
const ll MAXN = 2e5 + 5;
const ll ROOTN = 320;
const ll LOGN = 18;
const ll INF = 1e18 + 1022;
*/

#define MAXN 200005
#define inf 1000000009

vll g[MAXN];
bool centroid_marked[MAXN];
int subtree[MAXN], K, tmpans, ans;
map<ll,int> road, final;

int dfs_init(int a, int par)
{
	subtree[a] = 1;
	for(pll bb : g[a])
		if(bb.ff != par and !centroid_marked[bb.ff])
			subtree[a] += dfs_init(bb.ff, a);
	return subtree[a];
}

int getCentroid(int a, int par, int n)
{
	bool is_centroid = (n - subtree[a] <= n/2);
	int hvy = -1;
	for(pll bb : g[a])
		if(bb.ff != par and !centroid_marked[bb.ff])
		{
			is_centroid = is_centroid && (subtree[bb.ff] <= n/2);
			if(hvy == -1 || subtree[hvy] < subtree[bb.ff]) hvy = bb.ff;
		}
	if(is_centroid)
		return a;
	return getCentroid(hvy, a, n);
}

void calc(int a, int par, int dist, int lev)
{
	for(pll bb : g[a])
		if(bb.ff != par and !centroid_marked[bb.ff])
			calc(bb.ff, a, bb.ss + dist, lev+1);
	if(road.find(dist) != road.end()) road[dist] = min(road[dist], lev); else road[dist] = lev;
}

void dcmp(int root)
{
	road.clear();
	final.clear();
	final[0] = 0;
	road[0] = 0;
	tmpans = inf;
	int n = dfs_init(root, -1);
	int cen = getCentroid(root, -1, n);
	// cout<<"cen = "<<cen<<"\n";
	for(pll bb : g[cen])
		if(!centroid_marked[bb.ff])
		{
			calc(bb.ff, cen, bb.ss, 1);
			for(map<ll, int> :: iterator it = road.begin() ; it != road.end(); ++it)
				if(final.find(K-(it->ff)) != final.end()) tmpans = min(tmpans, final[K- (it->ff)] + it->ss);
			for(map<ll, int> :: iterator it = road.begin() ; it != road.end(); ++it)
				if(final.find((it->ff)) != final.end()) final[(it->ff)] = min(final[(it->ff)], it->ss);else final[(it->ff)] = it->ss;
		}
	// cout<<"here we have \n";
	// for(map<ll, int> :: iterator it = road.begin() ; it != road.end(); ++it)
	// 	cout<<"road["<<(it->ff)<<"] = "<<(it->ss)<<'\n';
	centroid_marked[cen] = true;
	ans = min(ans, tmpans);
	// if(tmpans != inf)
	// 	cerr<<"found tmpans = "<<tmpans<<" when cen  = "<<cen<<'\n';
	for(pll bb : g[cen])
		if(!centroid_marked[bb.ff])
			dcmp(bb.ff);
	// cout<<"tmpans = "<<tmpans<<'\n';
}

int best_path(int NN,int KK,int H[][2],int L[])
{
	K = KK;
	F0R(i, NN)
		centroid_marked[i] = false;
	F0R(i, NN-1)
		g[H[i][1]].pb(mp(H[i][0], L[i])), g[H[i][0]].pb(mp(H[i][1], L[i]));

	ans = inf;
	dcmp(0);
	return (ans == inf) ? -1 : ans;
}
/*
signed main()
{

	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	

	int N, KK;
	cin>>N>>KK;
	int H[N-1][2], L[N-1];
	F0R(i, N-1)
		cin>>H[i][0]>>H[i][1]>>L[i];

	cout<<best_path(N, KK, H, L);
	
	return 0;
}

4 3 
0 1 1
1 2 2
1 3 4

11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6 
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
*/

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