Submission #139436

#	Time	Username	Problem	Language	Result	Execution time	Memory
139436		claudy	Race (IOI11_race)	C++14	100 / 100	1788 ms	139276 KiB

race

# include "race.h"
//# pragma GCC optimize("Ofast,no-stack-protector")
//# pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
# pragma GCC optimize("Ofast")
# pragma GCC optimization ("unroll-loops")
# include "bits/stdc++.h"
/*
# include <ext/pb_ds/tree_policy.hpp>
# include <ext/pb_ds/assoc_container.hpp>
# include <ext/rope>
*/
std::pair<int,int> DR[] = {{-1,0},{0,1},{1,0},{0,-1},{-1,1},{-1,-1},{1,1},{1,-1}};
# define ll long long
# define clock (clock() * 1000.0 / CLOCKS_PER_SEC)
# define rc(s) return cout << s,0
# define rcg(s) cout << s;exit(0)
# define _ ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
# define db(x) cerr << #x << " = " << x << '\n'
# define pb push_back
# define mp make_pair
# define all(s) s.begin(),s.end()
# define sz(x) (int)((x).size())
# define int ll
using namespace std;

int dep[1 << 18],dep2[1 << 18],s[1 << 18],x,ans = 1e18,n,k;
vector<pair<int,int>>vec[1 << 18];
unordered_map<int,multiset<int>>ms;

inline void pre(int nod,int par,int val)
{
	dep[nod] = dep[par] + val;
	dep2[nod] = dep2[par] + 1;
	s[nod] = 1;
	for(auto it : vec[nod])
	{
		if(it.first != par)
		{
			pre(it.first,nod,it.second);
			s[nod] += s[it.first];
		}
	}
}

inline void add1_node(int nod,int gg)
{
	if(sz(ms[2 * gg + k - dep[nod]]))
	{
		x = min(x,dep2[nod] + *(ms[2 * gg + k - dep[nod]].begin()));
	}
}

inline void add2_node(int nod,int gg)
{
	ms[dep[nod]].insert(dep2[nod]);
}

inline void add1(int nod,int par,int gg)
{
	add1_node(nod,gg);
	for(auto it : vec[nod])
	{
		if(it.first != par)
		{
			add1(it.first,nod,gg);
		}
	}
}

inline void add2(int nod,int par,int gg)
{
	add2_node(nod,gg);
	for(auto it : vec[nod])
	{
		if(it.first != par)
		{
			add2(it.first,nod,gg);
		}
	}
}



inline void del_node(int nod)
{
	ms[dep[nod]].erase(ms[dep[nod]].find(dep2[nod]));
}

inline void del(int nod,int par)
{
	del_node(nod);
	for(auto it : vec[nod])
	{
		if(it.first != par)
		{
			del(it.first,nod);
		}
	}
}

inline void dfs(int nod,int par,bool keep)
{
	pair<int,int>mx = mp(-1,-1);
	for(auto it : vec[nod])
	{
		if(it.first != par)
		{
			mx = max(mx,mp(s[it.first],it.first));
		}
	}
	for(auto it : vec[nod])
	{
		if(it.first != par && it.first != mx.second)
		{
			dfs(it.first,nod,0);
		}
	}
	if(mx.second != -1) dfs(mx.second,nod,1);
	x = 1e18;
	add1_node(nod,dep[nod]);
	add2_node(nod,dep[nod]);
	for(auto it : vec[nod])
	{
		if(it.first != par && it.first != mx.second)
		{
			add1(it.first,nod,dep[nod]);
			add2(it.first,nod,dep[nod]);
		}
	}
	//cout << nod << ' ' << x << ' ' << x - 2 * dep2[nod] << '\n';
	if(x != 1e18) ans = min(ans,x - 2 * dep2[nod]);
	if(keep) return ;
	del(nod,par);
}

# undef int 
int best_path(int N, int K, int H[][2], int L[])
{
# define int ll
	k = K;
	n = N;
	for(int i = 0;i < n - 1;i++)
	{
		vec[H[i][0]].pb(mp(H[i][1],L[i]));
		vec[H[i][1]].pb(mp(H[i][0],L[i]));
	}
	pre(0,0,0);
	dfs(0,0,1);
	if(ans == 1e18) return -1;
	else return ans;
}

Compilation message (stderr)

race.cpp:5:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 # pragma GCC optimization ("unroll-loops")

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