Submission #691865

#	Time	Username	Problem	Language	Result	Execution time	Memory
691865		Markomafko972	Race (IOI11_race)	C++14	100 / 100	574 ms	38440 KiB

race

#include <bits/stdc++.h>
#include "race.h"
#define X first
#define Y second
#define pb push_back
#define pii pair<int, int>
typedef long long ll;
using namespace std;

const int MOD = 1e9 + 7;
const ll INF = 1e18;
const int OFF = (1 << 20);

int n, k, sol = 1e9;
vector< pair<int, int> > v[200005];
int kol[200005];
ll d[200005];
int bio[200005];
int w[1000005];

void dfs(int x, int p, ll dist) {
	d[x] = dist;
	kol[x]++;
	
	for (int i = 0; i < v[x].size(); i++) {
		if (v[x][i].X != p) {
			dfs(v[x][i].X, x, dist+v[x][i].Y);
			kol[x] += kol[v[x][i].X];
		}
	}
}

void postavi(int x, int p, ll l1, int l2) {
	if (l1 <= k) w[l1] = min(w[l1], l2);
	
	for (int i = 0; i < v[x].size(); i++) {
		if (v[x][i].X != p && bio[v[x][i].X] == 0) postavi(v[x][i].X, x, l1+v[x][i].Y, l2+1);
	}
}

void odstavi(int x, int p, ll l1, int l2) {
	if (l1 <= k) w[l1] = 1e9;
	
	for (int i = 0; i < v[x].size(); i++) {
		if (v[x][i].X != p && bio[v[x][i].X] == 0) odstavi(v[x][i].X, x, l1+v[x][i].Y, l2+1);
	}
}

void racunaj(int x, int p, ll l1, int l2) {
	if (l1 <= k && w[k-l1] != 1e9) sol = min(sol, w[k-l1]+l2);
	
	for (int i = 0; i < v[x].size(); i++) {
		if (v[x][i].X != p && bio[v[x][i].X] == 0) racunaj(v[x][i].X, x, l1+v[x][i].Y, l2+1);
	}
}

void centroidna(int x, int siz) {
	while (1) {
		int maxi = -1, gdje = -1;
		for (int i = 0; i < v[x].size(); i++) {
			if (bio[v[x][i].X] == 0 && kol[v[x][i].X] > maxi) {
				maxi = kol[v[x][i].X];
				gdje = v[x][i].X;
			}
		}
	
		if (maxi > siz/2) {
			int pri = kol[gdje];
			kol[gdje] = kol[x];
			kol[x] -= pri;
			x = gdje;
		}
		else break;
	}
	
	bio[x] = 1;
	w[0] = 0;
	for (int i = 0; i < v[x].size(); i++) {
		if (bio[v[x][i].X] == 0) {
			racunaj(v[x][i].X, x, v[x][i].Y, 1);
			postavi(v[x][i].X, x, v[x][i].Y, 1);
		}
	}
	for (int i = 0; i < v[x].size(); i++) {
		if (bio[v[x][i].X] == 0) odstavi(v[x][i].X, x, v[x][i].Y, 1);
	}
	w[0] = 1e9;
	
	for (int i = 0; i < v[x].size(); i++) {
		if (bio[v[x][i].X] == 0) centroidna(v[x][i].X, kol[v[x][i].X]);
	}
}

int best_path(int N, int K, int h[][2], int l[]) {

	n = N;
	k = K;
	
	for (int i = 0; i < n-1; i++) {
		v[h[i][0]].push_back({h[i][1], l[i]});
		v[h[i][1]].push_back({h[i][0], l[i]});
	}
	
	for (int i = 0; i <= k; i++) w[i] = 1e9;
	
	dfs(0, -1, 0);
	centroidna(0, n);
	if (sol == 1e9) return -1;
	else return sol;
}

Compilation message (stderr)

race.cpp: In function 'void dfs(int, int, ll)':
race.cpp:25:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  for (int i = 0; i < v[x].size(); i++) {
      |                  ~~^~~~~~~~~~~~~
race.cpp: In function 'void postavi(int, int, ll, int)':
race.cpp:36:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for (int i = 0; i < v[x].size(); i++) {
      |                  ~~^~~~~~~~~~~~~
race.cpp: In function 'void odstavi(int, int, ll, int)':
race.cpp:44:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  for (int i = 0; i < v[x].size(); i++) {
      |                  ~~^~~~~~~~~~~~~
race.cpp: In function 'void racunaj(int, int, ll, int)':
race.cpp:52:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for (int i = 0; i < v[x].size(); i++) {
      |                  ~~^~~~~~~~~~~~~
race.cpp: In function 'void centroidna(int, int)':
race.cpp:60:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |   for (int i = 0; i < v[x].size(); i++) {
      |                   ~~^~~~~~~~~~~~~
race.cpp:78:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  for (int i = 0; i < v[x].size(); i++) {
      |                  ~~^~~~~~~~~~~~~
race.cpp:84:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |  for (int i = 0; i < v[x].size(); i++) {
      |                  ~~^~~~~~~~~~~~~
race.cpp:89:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |  for (int i = 0; i < v[x].size(); i++) {
      |                  ~~^~~~~~~~~~~~~

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