Submission #7323

#	Time	Username	Problem	Language	Result	Execution time	Memory
7323		kriii	Race (IOI11_race)	C++98	100 / 100	801 ms	25836 KiB

race

#include "race.h"
#include <algorithm>
#include <vector>
using namespace std;
#define MAX_N 200001
#define MAX_K 1000001

const int non = 0x3fffffff;
vector<int> G[MAX_N];
int ex[MAX_N],ey[MAX_N],l[MAX_N],K;
bool forb[MAX_N];
int ts,chk[MAX_N],cut[MAX_N],Q[MAX_N],depth[MAX_N],len[MAX_N],sz[MAX_N],line[MAX_K];

int gety(int x, int i){
	return x == ex[i] ? ey[i] : ex[i];
}

int dfs(int x)
{
	int head, tail, res = non;

	head = tail = -1;
	Q[++head] = x; chk[x] = ts; depth[x] = 0;
	while (tail < head){
		int p = Q[++tail];
		for (int i=0;i<G[p].size();i++) if (!forb[G[p][i]]){
			int q = gety(p,G[p][i]);
			if (chk[q] != ts){
				Q[++head] = q;
				chk[q] = ts;
				depth[q] = depth[p] + 1;
			}
		}
	}
	ts++;
	int all = head + 1;

	if (all > 1){
		int c = x;
		for (int j=head;j>=0;j--){
			int p = Q[j];
			sz[p] = 1;

			bool good = true;
			for (int i=0;i<G[p].size();i++) if (!forb[G[p][i]]){
				int q = gety(p,G[p][i]);

				if (depth[p] < depth[q]){
					sz[p] += sz[q];
					if (sz[q] > all/2) good = false;
				}
			}
			if (all - sz[p] > all/2) good = false;

			if (good){
				c = p;
				break;
			}
		}

		int child = 0;
		head = tail = 0; x = c;
		Q[0] = x; chk[x] = ts; depth[x] = len[x] = 0; line[0] = 0;
		for (int i=0;i<G[x].size();i++) if (!forb[G[x][i]]){
			int y = gety(x,G[x][i]);
			cut[child++] = y;
			chk[y] = ts;
			depth[y] = 1;
			len[y] = l[G[x][i]];
		}

		for (int s=0;s<child;s++){
			int last = head;
			if (len[cut[s]] <= K) Q[++head] = cut[s];
			while (tail < head){
				int p = Q[++tail];
				res = min(res,line[K-len[p]]+depth[p]);
				for (int i=0;i<G[p].size();i++) if (!forb[G[p][i]]){
					int q = gety(p,G[p][i]);

					if (chk[q] != ts){
						chk[q] = ts;
						depth[q] = depth[p] + 1;
						len[q] = len[p] + l[G[p][i]];
						if (len[q] <= K) Q[++head] = q;
					}
				}
			}

			for (int j=last+1;j<=head;j++){
				int p = Q[j];
				line[len[p]] = min(line[len[p]],depth[p]);
			}
		}
		for (int j=0;j<=head;j++){
			line[len[Q[j]]] = non;
		}
		ts++;

		for (int i=0;i<G[x].size();i++) if (!forb[G[x][i]]){
			forb[G[x][i]] = 1;
			int small = dfs(gety(c,G[x][i]));
			res = min(res,small);
		}
	}

	return res;
}

int best_path(int N, int K_, int H[][2], int L[])
{
	K = K_;
	for (int i=0;i<N-1;i++){
		int x = H[i][0], y = H[i][1];
		G[x].push_back(i);
		G[y].push_back(i);
		ex[i] = x; ey[i] = y; l[i] = L[i];
	}
	for (int i=0;i<N;i++) chk[i] = -1;
	for (int i=0;i<=K;i++) line[i] = non;

	int ans = dfs(0);
	if (ans == non) ans = -1;
	return ans;
}

Compilation message (stderr)

race.cpp: In function 'int dfs(int)':
race.cpp:26:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0;i<G[p].size();i++) if (!forb[G[p][i]]){
                ~^~~~~~~~~~~~
race.cpp:45:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i=0;i<G[p].size();i++) if (!forb[G[p][i]]){
                 ~^~~~~~~~~~~~
race.cpp:64:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0;i<G[x].size();i++) if (!forb[G[x][i]]){
                ~^~~~~~~~~~~~
race.cpp:78:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<G[p].size();i++) if (!forb[G[p][i]]){
                  ~^~~~~~~~~~~~
race.cpp:100:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0;i<G[x].size();i++) if (!forb[G[x][i]]){
                ~^~~~~~~~~~~~

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