제출 #527016

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
527016		Hanksburger	경주 (Race) (IOI11_race)	C++17	100 / 100	484 ms	51756 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 u=vec[i];
		long long maxi=m-sz[u];
		for (long long j=0; j<adj[u].size(); j++)
		{
			long long v=adj[u][j].first;
			if (sz[u]>sz[v])
				maxi=max(maxi, sz[v]);
		}
		if (maxi<=m/2)
		{
			center=u;
			break;
		}
	}
//	cout << "center: " << center << '\n';
	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;
}

컴파일 시 표준 에러 (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:57: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]
   57 |   for (long long j=0; j<adj[u].size(); j++)
      |                       ~^~~~~~~~~~~~~~
race.cpp:70: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]
   70 |  for (long long i=0; i<adj[center].size(); i++)
      |                      ~^~~~~~~~~~~~~~~~~~~
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:76: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]
   76 |   for (long long j=0; j<val.size(); j++)
      |                       ~^~~~~~~~~~~
race.cpp:89: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]
   89 |  for (long long i=0; i<val2.size(); i++)
      |                      ~^~~~~~~~~~~~
race.cpp:92: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]
   92 |  for (long long i=0; i<adj[center].size(); i++)
      |                      ~^~~~~~~~~~~~~~~~~~~
race.cpp:95: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]
   95 |   for (long long j=0; j<adj[v].size(); j++)
      |                       ~^~~~~~~~~~~~~~

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