Submission #148110

#	Time	Username	Problem	Language	Result	Execution time	Memory
148110		WhipppedCream	Valley (BOI19_valley)	C++17	100 / 100	1203 ms	107572 KiB

valley

#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 (stderr)

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 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 41 / 41