Submission #101218

#	Time	Username	Problem	Language	Result	Execution time	Memory
101218		davitmarg	Race (IOI11_race)	C++17	100 / 100	1096 ms	36956 KiB

race

/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <iterator>
#include <ctype.h>
#include <stdlib.h>  
#include <cassert>
#include <fstream>

#ifndef death
#include "race.h"
#endif

#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;

int n, k, num[200005], used[200005], usedNum[200005], usedC[200005], wasC[200005], color = 1, cColor = 1, numColor = 1, ans = mod;
vector<pair<int, LL>> g[200005], upd;
vector<int> cl;
int dp[2000006];
void getNum(int v)
{
	usedNum[v] = numColor;
	num[v] = 1;
	for (int i = 0; i < g[v].size(); i++)
	{
		int to = g[v][i].first;
		if (usedNum[to] == numColor || wasC[to])
			continue;
		getNum(to);
		num[v] += num[to];
	}
}

int centroid(int v)
{
	numColor++;
	cColor++;
	getNum(v);
	int st = v;
	queue<int> q;
	q.push(v);
	while (!q.empty())
	{
		v = q.front();
		q.pop();
		usedC[v] = cColor;
		bool is = 1;
		for (int i = 0; i<g[v].size(); i++)
			if (num[g[v][i].first]>num[st] / 2 && usedC[g[v][i].first] != cColor && !wasC[g[v][i].first])
			{
				is = 0;
				q.push(g[v][i].first);
			}
		if (is)
		{
			wasC[v] = 1;
			return v;
		}
	}
}

void dfs(int v, LL sum, int depth)
{
	used[v] = color;

	if (sum <= k && dp[sum] == 0)
		dp[sum] = mod;
	if (k > sum && dp[k - sum] == 0)
		dp[k - sum] = mod;

	if (sum == k)
		ans = min(ans, depth);
	else if (sum < k)
		ans = min(ans, depth + dp[k - sum]);
	else
		return;

	cl.PB(sum);
	upd.PB(MP(depth, sum));

	for (int i = 0; i < g[v].size(); i++)
	{
		int to = g[v][i].first;
		LL D = g[v][i].second;
		if (used[to] == color || wasC[to])
			continue;
		dfs(to, sum + D, depth + 1);
	}
}

void solve(int v)
{
	color++;
	vector<int> nxt;
	for (int i = 0; i < g[v].size(); i++)
	{
		int to = g[v][i].first;
		LL D = g[v][i].second;
		if (used[to] == color || wasC[to])
			continue;

		upd.clear();
		dfs(to, D, 1);
		for (int j = 0; j < upd.size(); j++)
			dp[upd[j].second] = min(dp[upd[j].second], upd[j].first);
		nxt.PB(to);
	}
	while (!cl.empty())
	{
		dp[cl.back()] = 0;
		cl.pop_back();
	}
	for (int i = 0; i < nxt.size(); i++)
		solve(centroid(nxt[i]));
}

int Main()
{
	solve(centroid(1));
	if (ans == mod)
		ans = -1;
	return 0;
}

int best_path(int N, int K, int h[][2], int l[])
{
	n = N;
	k = K;
	for (int i = 0; i < n - 1; i++)
	{
		h[i][0]++;
		h[i][1]++;
		g[h[i][0]].PB(MP(h[i][1], l[i]));
		g[h[i][1]].PB(MP(h[i][0], l[i]));
	}
	Main();
	return ans;
}

#ifdef death
int main()
{
	cin >> n >> k;

	for (int i = 0; i < n - 1; i++)
	{
		int a, b;
		LL D;
		cin >> a >> b >> D;
		/*a = i;
		b = a + 1;
		D = rand() % 20;*/
		a++;
		b++;
		g[a].PB(MP(b, D));
		g[b].PB(MP(a, D));
	}
	Main();
	cout << ans << endl;
	return 0;
}
#endif

/*

*/

Compilation message (stderr)

race.cpp: In function 'void getNum(int)':
race.cpp:39:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < g[v].size(); i++)
                  ~~^~~~~~~~~~~~~
race.cpp: In function 'int centroid(int)':
race.cpp:63:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i<g[v].size(); i++)
                   ~^~~~~~~~~~~~
race.cpp: In function 'void dfs(int, long long int, int)':
race.cpp:96:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < g[v].size(); i++)
                  ~~^~~~~~~~~~~~~
race.cpp: In function 'void solve(int)':
race.cpp:110:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < g[v].size(); i++)
                  ~~^~~~~~~~~~~~~
race.cpp:119:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < upd.size(); j++)
                   ~~^~~~~~~~~~~~
race.cpp:128:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < nxt.size(); i++)
                  ~~^~~~~~~~~~~~
race.cpp: In function 'int centroid(int)':
race.cpp:75:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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