Submission #101180

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
101180	2019-03-17T08:54:16 Z	davitmarg	Race (IOI11_race)	C++17	Compilation error	0 ms	0 KB

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, d[200005], used[200005], used1[200005], usedc[200005], ans = mod;
vector<pair<int, LL>> g[200005];
map<LL, int> dp;
vector<pair<LL, int>> upd;
void dfs1(int v)
{
	usedc[v] = 1;
	d[v] = 1;
	for (int i = 0; i<g[v].size(); i++)
	{
		int to = g[v][i].first;
		if (usedc[to])
			continue;
		dfs1(to);
		d[v] += d[to];
	}
}

int centroid(int v)
{
	usedc[v] = 1;
	for (int i = 0; i<g[v].size(); i++)
	{
		int to = g[v][i].first;
		if (usedc[to])
			continue;
		if (d[to] > d[v] / 2)
			return centroid(to);
	}
	return v;
}

void dfs(int v, LL dist, int depth)
{
	used[v] = 1;

	if (dp[dist] == 0)
		dp[dist] = mod;

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

	upd.PB(MP(dist, depth));

	if (k > dist)
		ans = min(depth + dp[k - dist], ans);
	else if (dist == k)
		ans = min(depth, ans);

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

void solve(int v)
{
	used1[v] = 1;
	usedc[v] = 1;
	vector<int> nxt;
	dp.clear();
	memset(used, 0, sizeof(int)*(n + 2));
	used[v] = 1;
	for (int i = 0; i<g[v].size(); i++)
	{
		int to = g[v][i].first;
		LL D = g[v][i].second;
		if (used1[to])
			continue;
		nxt.PB(to);
		upd.resize(0);
		dfs(to, D, 1);
		for (int j = 0; j < upd.size(); j++)
			dp[upd[j].first] = min(upd[j].second, dp[upd[j].first]);
	}
	for (int i = 0; i < nxt.size(); i++)
		solve(centroid(nxt[i]));
}

int Main()
{
	dfs1(1);
	memset(usedc, 0, sizeof(int)*(n + 2));
	int c = centroid(1);
	memset(usedc, 0, sizeof(int)*(n + 2));
	solve(c);
	if (ans == mod)
		ans = -1;
	return 0;
}

LL best_path(int N, int K, vector<vector<int>> h, vector<LL> l)
{
	n = N;
	k = K;
	reverse(all(l));
	for (int i = 0; i < h.size(); i++)
	{
		h[i][0]++;
		for (int j = 1; j < h[i].size(); j++)
		{
			h[i][j]++;
			g[h[i][0]].PB(MP(h[i][j], l.back()));
			g[h[i][j]].PB(MP(h[i][0], l.back()));
			l.pop_back();
		}
	}
	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++;
		b++;
		g[a].PB(MP(b, D));
		g[b].PB(MP(a, D));
	}
	Main();
	cout << ans << endl;
	return 0;
}
#endif

/*

*/

Compilation message

race.cpp: In function 'void dfs1(int)':
race.cpp:39:19: 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:52:19: 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:80:19: 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:98:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i<g[v].size(); i++)
                  ~^~~~~~~~~~~~
race.cpp:107:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < upd.size(); j++)
                   ~~^~~~~~~~~~~~
race.cpp:110:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < nxt.size(); i++)
                  ~~^~~~~~~~~~~~
race.cpp: In function 'long long int best_path(int, int, std::vector<std::vector<int> >, std::vector<long long int>)':
race.cpp:131:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < h.size(); i++)
                  ~~^~~~~~~~~~
race.cpp:134:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 1; j < h[i].size(); j++)
                   ~~^~~~~~~~~~~~~
/tmp/ccyLKM5L.o: In function `main':
grader.cpp:(.text.startup+0x20): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status