Submission #527015

#	Time	Username	Problem	Language	Result	Execution time	Memory
527015		Hanksburger	Race (IOI11_race)	C++17	0 / 100	3 ms	4940 KiB

race

#include <bits/stdc++.h>
using namespace std;
long long dp[1000005], sz[200005], n, k, ans=1e18;
vector<pair<long long, long long> > adj[200005], val;
vector<long long> val2, tmp;
void dfs(long long u, long long prev)
{
	sz[u]=1;
	for (long long i=0; i<adj[u].size(); i++)
	{
		long long v=adj[u][i].first;
		if (v==prev)
			continue;
		dfs(v, u);
		sz[u]+=sz[v];
	}
}
void dfs2(long long u, long long prev, long long cnt, long long cur)
{
	if (cur>k)
		return;
	val.push_back({cnt, cur});
	val2.push_back(cur);
	for (long long i=0; i<adj[u].size(); i++)
	{
		long long v=adj[u][i].first, w=adj[u][i].second;
		if (v==prev)
			continue;
		dfs2(v, u, cnt+1, cur+w);
	}
}
void dfs3(long long u, long long prev)
{
	tmp.push_back(u);
	for (long long i=0; i<adj[u].size(); i++)
	{
		long long v=adj[u][i].first;
		if (v==prev)
			continue;
		dfs3(v, u);
	}
}
void recur(vector<long long> vec)
{
//	cout << "vec: ";
//	for (long long i=0; i<vec.size(); i++)
//		cout << vec[i] << ' ';
//	cout << '\n';
	long long m=vec.size(), center;
	if (m==1)
		return;
	dfs(vec[0], -1);
	for (long long i=0; i<m; i++)
	{
		long long maxi=m-sz[i];
		for (long long j=0; j<adj[i].size(); j++)
		{
			long long v=adj[i][j].first;
			if (sz[i]>sz[v])
				maxi=max(maxi, sz[v]);
		}
		if (maxi<=m/2)
		{
			center=i;
			break;
		}
	}
	for (long long i=0; i<adj[center].size(); i++)
	{
		long long v=adj[center][i].first, w=adj[center][i].second;
		dfs2(v, center, 1, w);
		for (long long j=0; j<val.size(); j++)
			ans=min(ans, dp[k-val[j].second]+val[j].first);
		for (long long j=0; j<val.size(); j++)
			dp[val[j].second]=min(dp[val[j].second], val[j].first);
//		cout << "val: ";
//		for (long long j=0; j<val.size(); j++)
//			cout << val[j].first << ' ' << val[j].second << ' ';
//		cout << '\n';
		val.clear();
//		cout << "dp: ";
//		for (long long j=0; j<=k; j++)
//			cout << dp[j] << ' ';
//		cout << '\n';
//		cout << "ans: " << ans << '\n';
	}
	for (long long i=0; i<val2.size(); i++)
		dp[val2[i]]=1e18;
	val2.clear();
	for (long long i=0; i<adj[center].size(); i++)
	{
		long long v=adj[center][i].first;
		for (long long j=0; j<adj[v].size(); j++)
		{
			if (adj[v][j].first==center)
			{
				adj[v].erase(adj[v].begin()+j);
				break;
			}
		}
		tmp.clear();
		dfs3(v, center);
		recur(tmp);
	}
}
int best_path(int N, int K, int H[][2], int L[])
{
	n=N;
	k=K;
	for (long long i=0; i<=n-2; i++)
	{
		adj[H[i][0]].push_back({H[i][1], L[i]});
		adj[H[i][1]].push_back({H[i][0], L[i]});
	}
	for (long long i=1; i<=k; i++)
		dp[i]=1e18;
	for (long long i=0; i<n; i++)
		tmp.push_back(i);
	recur(tmp);
	if (ans==1e18)
		return -1;
	return ans;
}

Compilation message (stderr)

race.cpp: In function 'void dfs(long long int, long long int)':
race.cpp:9:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |  for (long long i=0; i<adj[u].size(); i++)
      |                      ~^~~~~~~~~~~~~~
race.cpp: In function 'void dfs2(long long int, long long int, long long int, long long int)':
race.cpp:24:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for (long long i=0; i<adj[u].size(); i++)
      |                      ~^~~~~~~~~~~~~~
race.cpp: In function 'void dfs3(long long int, long long int)':
race.cpp:35:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  for (long long i=0; i<adj[u].size(); i++)
      |                      ~^~~~~~~~~~~~~~
race.cpp: In function 'void recur(std::vector<long long int>)':
race.cpp:56:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |   for (long long j=0; j<adj[i].size(); j++)
      |                       ~^~~~~~~~~~~~~~
race.cpp:68:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |  for (long long i=0; i<adj[center].size(); i++)
      |                      ~^~~~~~~~~~~~~~~~~~~
race.cpp:72:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   for (long long j=0; j<val.size(); j++)
      |                       ~^~~~~~~~~~~
race.cpp:74:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |   for (long long j=0; j<val.size(); j++)
      |                       ~^~~~~~~~~~~
race.cpp:87:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |  for (long long i=0; i<val2.size(); i++)
      |                      ~^~~~~~~~~~~~
race.cpp:90:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |  for (long long i=0; i<adj[center].size(); i++)
      |                      ~^~~~~~~~~~~~~~~~~~~
race.cpp:93:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |   for (long long j=0; j<adj[v].size(); j++)
      |                       ~^~~~~~~~~~~~~~

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