Submission #349849

#	Time	Username	Problem	Language	Result	Execution time	Memory
349849		NachoLibre	경주 (Race) (IOI11_race)	C++11	43 / 100	616 ms	59756 KiB

race

#include <bits/stdc++.h>
using namespace std;
#ifndef wambule
#include "race.h"
#endif

const int N = 200005, K = 1000006;
int mn, globk, ak[K], fp = -1;
vector<pair<int, int>> v[N], ve;
bool bo[N];

inline void minn(int &a, int b) {
	if(a == -1 || b < a) a = b;
}

int ctr(int dg, int op) {
	int dr = mn - 1, y;
	bool mo = 1;
	for(int i = 0; i < v[dg].size(); ++i) {
		if(v[dg][i].first != op && !bo[v[dg][i].first]) {
			y = ctr(v[dg][i].first, dg);
			if(y < 0) return y;
			if(y > mn / 2) mo = 0;
			dr -= y;
		}
	}
	if(dr > mn / 2) mo = 0;
	if(mo) return -dg;
	return mn - dr;
}

int sra(int dg, int op) {
	int dr = 1;
	for(int i = 0; i < v[dg].size(); ++i) {
		if(v[dg][i].first != op && !bo[v[dg][i].first]) {
			dr += sra(v[dg][i].first, dg);
		}
	}
	return dr;
}

int cntr(int x = 0) {
	mn = sra(x, -1);
	return -ctr(x, -1);
}

void ovo(int dg, int op, int wr, int md) {
	// cout << "[ovog] " << dg << "\n";
	if(md > globk) return;
	ve.push_back({wr, md});
	for(int i = 0; i < v[dg].size(); ++i) {
		if(v[dg][i].first != op && !bo[v[dg][i].first]) {
			ovo(v[dg][i].first, dg, wr + 1, md + v[dg][i].second);
		}
	}
}

void ama(int dg) {
	// cout << "[cntr] " << dg << "\n";
	bo[dg] = 1;
	stack<int> vey;
	for(int i = 0; i < v[dg].size(); ++i) {
		if(!bo[v[dg][i].first]) {
			ve.clear();
			ovo(v[dg][i].first, -1, 1, v[dg][i].second);
			for(int j = 0; j < ve.size(); ++j) {
				// cout << "[vepm] " << ve[i].first << " " << ve[i].second << "\n";
				if(ve[j].second == globk) minn(fp, ve[j].first);
				else {
					vey.push(ve[j].second);
					if(ak[globk - ve[j].second]) {
						minn(fp, ak[globk - ve[j].second] + ve[j].first);
					}
				}
			}
			for(int j = 0; j < ve.size(); ++j) {
				if(ak[ve[j].second] == 0 || ak[ve[j].second] > ve[j].first) {
					ak[ve[j].second] = ve[j].first;
				}
			}
		}
	}
	while(vey.size()) {
		ak[vey.top()] = 0;
		vey.pop();
	}
	for(int i = 0; i < v[dg].size(); ++i) {
		int x = v[dg][i].first;
		if(!bo[x]) ama(cntr(x));
	}
}

int best_path(int n, int k, int h[][2], int l[]) {
	globk = k;
	for(int i = 0; i < n; ++i) {
		v[i].clear();
		bo[i] = 0;
	}
	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]});
	}
	ama(cntr());
	return fp;
}

#ifdef wambule
mt19937_64 rnd(time(0));

long long R(long long l, long long r) {
	return 1ll * rnd() % (r - l + 1) + l;
}

long long Sr(long long r) {
	return R(0, r - 1);
}

void G(int n, int h[][2]) {
	vector<int> v;
	for(int i = 0; i < n; ++i) {
		v.push_back(i);
	}
	random_shuffle(v.begin(), v.end());
	for(int i = 0; i < n - 1; ++i) {
		h[i][0] = v[R(0, i)];
		h[i][1] = v[i + 1];
	}
}

int h[N][2];
int l[N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	srand(time(0));
	cin.get();
	// int n = 11;
	// int k = 12;
	// int h[][2] = {0, 1, 0, 2, 2, 3, 3, 4, 4, 5, 0, 6, 6, 7, 6, 8, 8, 9, 8, 10};
	// int l[]    = {3, 4, 5, 4, 6, 3, 2, 5, 6, 7};
	int n = 200000;
	int k = 1000000;
	G(n, h);
	for(int i = 0; i < n - 1; ++i) {
		l[i] = R(0, 1000000);
	}
	int rtnd = best_path(n, k, h, l);
	cout << "[fnps] " << rtnd << endl;
	return 0;
}
#endif

Compilation message (stderr)

race.cpp: In function 'int ctr(int, int)':
race.cpp:19:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |  for(int i = 0; i < v[dg].size(); ++i) {
      |                 ~~^~~~~~~~~~~~~~
race.cpp: In function 'int sra(int, int)':
race.cpp:34:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  for(int i = 0; i < v[dg].size(); ++i) {
      |                 ~~^~~~~~~~~~~~~~
race.cpp: In function 'void ovo(int, int, int, int)':
race.cpp:51:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |  for(int i = 0; i < v[dg].size(); ++i) {
      |                 ~~^~~~~~~~~~~~~~
race.cpp: In function 'void ama(int)':
race.cpp:62:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |  for(int i = 0; i < v[dg].size(); ++i) {
      |                 ~~^~~~~~~~~~~~~~
race.cpp:66: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]
   66 |    for(int j = 0; j < ve.size(); ++j) {
      |                   ~~^~~~~~~~~~~
race.cpp:76: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]
   76 |    for(int j = 0; j < ve.size(); ++j) {
      |                   ~~^~~~~~~~~~~
race.cpp:87:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |  for(int i = 0; i < v[dg].size(); ++i) {
      |                 ~~^~~~~~~~~~~~~~

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