oj.uz

Submission #148110

# Submission time Handle Problem Language Result Execution time Memory
148110 2019-08-31T13:59:23 Z WhipppedCream Valley (BOI19_valley) C++17
100 / 100
 1203 ms 107572 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;

const int maxn = 1e5+5;

int n, k, q, e;

int len[maxn];
vector< ii > way[maxn];
vector< ii > adj[maxn];
int mp[maxn];
int sigan = 0;

struct node
{
	int key, pr;
	ll val, opt;
	node *left, *right;
	node(int key, ll val) : key(key), val(val)
	{
		opt = val;
		pr = (rand()<<16)^rand();
		left = right = NULL;
	}
	void calc()
	{
		opt = val;
		if(left) opt = min(left->opt, opt);
		if(right) opt = min(right->opt, opt);
	}
};

typedef node* ps;

ps merge(ps L, ps R)
{
	if(!L || !R) return L?L:R;
	if(L->pr> R->pr)
	{
		L->right = merge(L->right, R);
		L->calc();
		return L;
	}
	else
	{
		R->left = merge(L, R->left);
		R->calc();
		return R;
	}
}

pair<ps, ps> split(ps big, int key)
{
	if(!big) return {NULL, NULL};
	int here = big->key;
	if(here<= key)
	{
		auto tmp = split(big->right, key);
		big->right = tmp.X;
		big->calc();
		return {big, tmp.Y};
	}
	else
	{
		auto tmp = split(big->left, key);
		big->left = tmp.Y;
		big->calc();
		return {tmp.X, big};
	}
}

int road[maxn];

void renumb(int u = 1, int p = 0)
{
	sigan++;
	mp[u] = sigan;
	for(auto vv : way[u])
	{
		int v = vv.X, id = vv.Y;
		if(v == p) continue;
		// printf("road[%d] = %d\n", id, v);
		road[id] = v;
		renumb(v, u);
	}
}

int cnt[maxn];
bitset<maxn> ban;

void findcnt(int u, int p)
{
	cnt[u] = 1;
	for(ii vv : adj[u])
	{
		int v = vv.X;
		if(v == p || ban[v]) continue;
		findcnt(v, u);
		cnt[u] += cnt[v];
	}
}

int gimme(int u, int p, int tot)
{
	for(ii vv : adj[u])
	{
		int v = vv.X;
		if(v == p || ban[v]) continue;
		if(2*cnt[v]> tot)
		{
			return gimme(v, u, tot);
		}
	}
	return u;
}

bitset<maxn> isshop;

ps root[maxn];

void solve(int u, int p, int cent, ll cur_dep)
{
	// printf("go %d %lld\n", u, cur_dep);
	if(isshop[u])
	{
		// add (u, cur_dep) to root[cent]
		// printf("beginning to add\n");
		auto tmp = split(root[cent], u);
		// printf("split ok\n");
		ps tmp2 = merge(tmp.X, new node(u, cur_dep));
		root[cent] = merge(tmp2, tmp.Y);
		// printf("add (%d, %lld) to centroid %d\n", u, cur_dep, cent);
	}
	for(ii vv : adj[u])
	{
		int v = vv.X, w = vv.Y;
		if(v == p || ban[v]) continue;
		solve(v, u, cent, cur_dep+len[w]);
	}
}

int par[maxn];

void centroid(int u, int lst)
{
	findcnt(u, 0);
	// printf("kuy\n");
	int tot = cnt[u];
	int cent = gimme(u, 0, tot);
	par[cent] = lst;
	solve(cent, 0, cent, 0);
	ban[cent] = true;
	for(ii vv : adj[cent])
	{
		int v = vv.X;
		if(ban[v]) continue;
		centroid(v, cent);
	}
}

ll from[maxn];
int dep[maxn];
int dp[21][maxn];

void util(int u = 1, int p = 0)
{
	dep[u] = dep[p]+1;
	dp[0][u] = p;
	for(int i = 1; i<= 20; i++) dp[i][u] = dp[i-1][dp[i-1][u]];
	for(ii vv : adj[u])
	{
		int v = vv.X, w = vv.Y;
		if(v == p) continue;
		from[v] = from[u]+len[w];
		util(v, u);
	}
}

int LCA(int u, int v)
{
	if(dep[u]< dep[v]) swap(u, v);
	for(int i = 20; i>= 0; i--)
	{
		int x = dp[i][u];
		if(dep[x]>= dep[v]) u = x;
	}
	if(u == v) return u;
	for(int i = 20; i>= 0; i--)
	{
		if(dp[i][u] == dp[i][v]) continue;
		u = dp[i][u]; v = dp[i][v];
	}
	return dp[0][u];
}

ll getDist(int u, int v)
{
	int x = LCA(u, v);
	return from[u]+from[v]-from[x]-from[x];
}

int main()
{
	scanf("%d %d %d %d", &n, &k, &q, &e);
	for(int i = 1; i< n; i++)
	{
		int u, v, w;
		scanf("%d %d %d", &u, &v, &w);
		way[u].pb(ii(v, i));
		way[v].pb(ii(u, i));
		len[i] = w;
	}
	renumb();
	for(int i = 1; i<= n; i++)
	{
		int u = mp[i];
		for(auto vv : way[i])
		{
			int v = mp[vv.X], id = vv.Y;
			assert(u != v);
			adj[u].pb(ii(v, id));
			adj[v].pb(ii(u, id));
		}
	}
	for(int i = 1; i<= n; i++)
	{
		sort(adj[i].begin(), adj[i].end());
		adj[i].resize(unique(adj[i].begin(), adj[i].end())-adj[i].begin());
	}
	for(int i = 1; i< n; i++)
	{
		road[i] = mp[road[i]];
	}
	for(int i = 1; i<= k; i++)
	{
		int x; scanf("%d", &x);
		isshop[mp[x]] = true;
	}
	// printf("kuy\n");
	centroid(1, 0);
	// printf("okay\n");
	ban.reset();
	findcnt(1, 0);
	util();
	e = mp[e];
	for(int qq = 1; qq<= q; qq++)
	{
		int r, me; scanf("%d %d", &r, &me);
		int st = road[r];
		me = mp[me];
		bool intree = (st<= me && me<= st+cnt[st]-1);
		bool eintree = (st<= e && e<= st+cnt[st]-1);
		if(intree == eintree)
		{
			printf("escaped\n");
			continue;
		}
		int cur = me;
		ll best = 1e18;
		while(cur> 0)
		{
			bool curintree = (st<= cur && cur<= st+cnt[st]-1);
			if(curintree != intree)
			{
				cur = par[cur];
				continue;
			}
			ll go = getDist(cur, me);
			auto tmp = split(root[cur], st-1);
			auto tmp2 = split(tmp.Y, st+cnt[st]-1);
			if(intree)
			{
				if(tmp2.X) best = min(best, go+(tmp2.X)->opt);
			}
			else
			{
				if(tmp.X) best = min(best, go+(tmp.X)->opt);
				if(tmp2.Y) best = min(best, go+(tmp2.Y)->opt);
			}
			auto tmp3 = merge(tmp2.X, tmp2.Y);
			root[cur] = merge(tmp.X, tmp3);
			cur = par[cur];
		}
		if(best == 1e18) printf("oo\n");
		else printf("%lld\n", best);
	}
}

Compilation message

valley.cpp: In function 'int main()':
valley.cpp:211:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d %d", &n, &k, &q, &e);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:215:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &u, &v, &w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:243:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x; scanf("%d", &x);
          ~~~~~^~~~~~~~~~
valley.cpp:255:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int r, me; scanf("%d %d", &r, &me);
              ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 5372 KB Output is correct
2 Correct 11 ms 5368 KB Output is correct
3 Correct 11 ms 5368 KB Output is correct
4 Correct 13 ms 5372 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 5372 KB Output is correct
2 Correct 11 ms 5368 KB Output is correct
3 Correct 11 ms 5368 KB Output is correct
4 Correct 13 ms 5372 KB Output is correct
5 Correct 9 ms 5496 KB Output is correct
6 Correct 8 ms 5496 KB Output is correct
7 Correct 9 ms 5500 KB Output is correct
8 Correct 9 ms 5496 KB Output is correct
9 Correct 10 ms 5496 KB Output is correct
10 Correct 10 ms 5496 KB Output is correct
11 Correct 10 ms 5624 KB Output is correct
12 Correct 10 ms 5652 KB Output is correct
13 Correct 11 ms 5880 KB Output is correct
14 Correct 9 ms 5496 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 504 ms 54736 KB Output is correct
2 Correct 617 ms 73000 KB Output is correct
3 Correct 835 ms 85272 KB Output is correct
4 Correct 1203 ms 99120 KB Output is correct
5 Correct 852 ms 99488 KB Output is correct
6 Correct 1132 ms 107572 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 5372 KB Output is correct
2 Correct 11 ms 5368 KB Output is correct
3 Correct 11 ms 5368 KB Output is correct
4 Correct 13 ms 5372 KB Output is correct
5 Correct 9 ms 5496 KB Output is correct
6 Correct 8 ms 5496 KB Output is correct
7 Correct 9 ms 5500 KB Output is correct
8 Correct 9 ms 5496 KB Output is correct
9 Correct 10 ms 5496 KB Output is correct
10 Correct 10 ms 5496 KB Output is correct
11 Correct 10 ms 5624 KB Output is correct
12 Correct 10 ms 5652 KB Output is correct
13 Correct 11 ms 5880 KB Output is correct
14 Correct 9 ms 5496 KB Output is correct
15 Correct 504 ms 54736 KB Output is correct
16 Correct 617 ms 73000 KB Output is correct
17 Correct 835 ms 85272 KB Output is correct
18 Correct 1203 ms 99120 KB Output is correct
19 Correct 852 ms 99488 KB Output is correct
20 Correct 1132 ms 107572 KB Output is correct
21 Correct 345 ms 30456 KB Output is correct
22 Correct 404 ms 30088 KB Output is correct
23 Correct 479 ms 30236 KB Output is correct
24 Correct 559 ms 32088 KB Output is correct
25 Correct 479 ms 33768 KB Output is correct
26 Correct 329 ms 30456 KB Output is correct
27 Correct 378 ms 30152 KB Output is correct
28 Correct 453 ms 30156 KB Output is correct
29 Correct 557 ms 32328 KB Output is correct
30 Correct 539 ms 34308 KB Output is correct
31 Correct 329 ms 32972 KB Output is correct
32 Correct 434 ms 34648 KB Output is correct
33 Correct 469 ms 35832 KB Output is correct
34 Correct 760 ms 38968 KB Output is correct
35 Correct 506 ms 41464 KB Output is correct
36 Correct 527 ms 50992 KB Output is correct