Submission #387907

#	Time	Username	Problem	Language	Result	Execution time	Memory
387907		pure_mem	Race (IOI11_race)	C++14	21 / 100	224 ms	20524 KiB

race

#include "race.h"
#include <bits/stdc++.h>

#define X first
#define Y second
#define ll long long
#define MP make_pair

using namespace std;

const int MAXN = 4e5 + 12;

int rnd(){
	return ((rand() << 15) + rand());
}

struct node{
	int l = 0, r = 0, pr = 0, tt2 = 0, dval = 0;
	ll val = 0, tt1 = 0;
	void init(ll _val, int _dval){
		l = r = 0, tt1 = tt2 = 0;
		val = _val, dval = _dval, pr = rnd();	
	}
}t[MAXN];
int root, tSize;
void push(int v){
	assert(tSize + 1 < MAXN);
	if(!v || !t[v].tt2)
		return;
	int l = t[v].l, r = t[v].r;
	if(l){
		t[l].val += t[v].tt1, t[l].tt1 += t[v].tt1;
		t[l].dval += t[v].tt2, t[l].tt2 += t[v].tt2;
	}
	if(r){
		t[r].val += t[v].tt1, t[r].tt1 += t[v].tt1;
		t[r].dval += t[v].tt2, t[r].tt2 += t[v].tt2;
	}
	t[v].tt1 = t[v].tt2 = 0;
}
void walk(int v){
	if(!v)
		return;
	push(v);
	walk(t[v].l);
	cerr << t[v].val << "\n";
	walk(t[v].r);
}
void split(int v, int &l, int &r, ll val){
	push(v);
	if(!v)
		return void(l = r = 0);
	if(val < t[v].val)
		split(t[v].l, l, t[v].l, val), r = v;
	else
		split(t[v].r, t[v].r, r, val), l = v;
}
void merge(int &v, int l, int r){
	if(!l || !r)
		return void(v = l ? l: r);
	if(t[l].pr > t[r].pr){
		push(l);
		merge(t[l].r, t[l].r, r), v = l;	
	}
	else{
		push(r);
		merge(t[r].l, l, t[r].l), v = r;
	}
}
void insert(int &v, int oth){
	push(v);
	if(!v)
		v = oth;
	else if(t[v].pr < t[oth].pr){
		split(v, t[oth].l, t[oth].r, t[oth].val), v = oth;
	}
	else{
		if(t[oth].val < t[v].val)
			insert(t[v].l, oth);
		else
			insert(t[v].r, oth);
	}
}
int isGood(int v, ll val, int dval){
	push(v);
	if(!v)
		return 0;
	if(t[v].val == val){
		t[v].dval = min(t[v].dval, dval);
		return t[v].dval;
	}
	else if(val < t[v].val)
		return isGood(t[v].l, val, dval);
	else
		return isGood(t[v].r, val, dval);
}

int answer, n, k, sz[MAXN];
vector< pair<int, int> > graph[MAXN];

void dfs_sz(int v, int pr){
	sz[v] = 1;
	for(pair<int, int> to: graph[v]){
		if(to.X != pr){
			dfs_sz(to.X, v);
			sz[v] += sz[to.X];
		}
	}	
}

void dfs_prep(int v, int pr, ll cost, int dist){
	if(cost > k)
		return;
	int tmp = isGood(root, k - cost, n + 12);
	if(tmp)
		answer = min(answer, tmp + dist);
	for(pair<int, int> to: graph[v]){
		if(to.X == pr)
			continue;
		dfs_prep(to.X, v, cost + to.Y, dist + 1);
	}
}

void dfs_add(int v, int pr, ll cost, int dist){
	if(cost > k)
		return;
	if(!isGood(root, cost, dist)){
		t[++tSize].init(cost, dist);
		insert(root, tSize);
	}
	for(pair<int, int> to: graph[v]){
		if(to.X == pr)
			continue;
		dfs_add(to.X, v, cost + to.Y, dist + 1);
	}
}



void dfs(int v, int pr, bool keep){
	int mx = 0, cost = 0;
	for(pair<int, int> to: graph[v]){
		if(to.X != pr && sz[mx] < sz[to.X])
			mx = to.X, cost = to.Y;
	}
	for(pair<int, int> to: graph[v]){
		if(to.X != pr && mx != to.X)
			dfs(to.X, v, 0);
	}
	if(mx){
		dfs(mx, v, 1);
		if(root)
			t[root].val += cost, t[root].dval += 1, t[root].tt1 += cost, t[root].tt2 += 1;
		int tmp = isGood(root, k, n + 12);
		if(tmp)
			answer = min(answer, tmp);
	}
	t[++tSize].init(0, 1);
	insert(root, tSize);
	for(pair<int, int> to: graph[v]){
		if(to.X != pr && mx != to.X)
			dfs_prep(to.X, v, to.Y, 1), dfs_add(to.X, v, to.Y, 2);
	}
	if(!keep)
		root = 0, tSize = 0;
}

int best_path(int N, int K, int H[][2], int L[]) {
	answer = N + 1, n = N, k = K;
	for(int i = 0;i < n;i++){
		graph[H[i][0] + 1].push_back(MP(H[i][1] + 1, L[i]));
		graph[H[i][1] + 1].push_back(MP(H[i][0] + 1, L[i]));
	}
	dfs_sz(1, 1);
	dfs(1, 1, 0);
	if(answer == N + 1)
		answer = -1;
	else
		answer -= 1;
	return answer;
}

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