Submission #452109

#	Time	Username	Problem	Language	Result	Execution time	Memory
452109		naman1601	Valley (BOI19_valley)	C++17	23 / 100	2433 ms	73760 KiB

valley

/*
++[---------->+<]>.-[------>+<]>-.++++++++.+++++.-[->+++++<]>-.-[--->++<]>--.+.[--->+<]>---.[->+++<]>++.++++++.-------.++++++.--[--->+<]>.-[->+++<]>-..+++++++++++++.[----->++<]>.------------.+[----->+<]>.--------.+++++++++++++.-------------.--[--->+<]>-.---[->++++<]>-.++++[->+++<]>.--[--->+<]>-.[->+++<]>++.-.+++.---.-[->+++<]>.-[--->++<]>+.++++.------.[--->+<]>---.+[----->+<]>.------------.+++++++.-------.--[--->+<]>---.+++[->+++<]>++..+++++++++.---------.-[->+++<]>.+[----->+<]>+.-------------.+++++++.+.----[->+++<]>-.
*/
#include <bits/stdc++.h>
using namespace std;

typedef long long big;
typedef long double ludo;
#define pbb pair<big, big>
#define pii pair<int, int>
#define fe first
#define se second
#define maxheap priority_queue
#define mset multiset
#define uset unordered_set
#define umap unordered_map
#define fr(i, s, e) for(int i = s; i < e; i++)
#define revfr(i, s, e) for(int i = s - 1; i >= e; i--)
#define getv(v, n) for(int i = 0; i < n; i++) cin >> v[i];
#define speed ios_base::sync_with_stdio(false); cin.tie(NULL)
#define nl "\n"
// #define debug(text) if(do_debug) {cout << (#text) << ": " << text << endl;}
#ifdef naman1601
#define debug(text) cout << (#text) << ": " << text << endl;
#else
#define debug(text)
#endif

const big mod = 1000000007;
// const big mod = 998244353;
const big infinity = 1000000000000000000;
const int inf = 1e9 + 5;
bool do_debug = false;


const int maxn = 1e5 + 5;
int n_nodes, nq, n_shops, destination;
vector<int> adj[maxn];
map<int, int> edge_wt[maxn];
int blocked[maxn] = {0};


struct binlift {

	int maxn, maxjump;
	vector<vector<int>> parent_table;
	vector<vector<big>> wt_table;
	vector<int> logtable;

	void init(int n, int jump) {

		maxn = n;
		maxjump = jump;
		parent_table = vector<vector<int>>(maxn, vector<int>(maxjump));
		wt_table = vector<vector<big>>(maxn, vector<big>(maxjump));
		logtable = vector<int>(maxn + 1, 0);

		logtable[1] = 0;

		fr(i, 2, maxn + 1) {

			logtable[i] = logtable[i >> 1] + 1;
		}
	}

	void add_node(int v, int p, big w) {

		parent_table[v][0] = p;
		wt_table[v][0] = w;
	}

	void build() {

		fr(j, 1, maxjump) {

			fr(v, 0, maxn) {

				if(parent_table[v][j - 1] != -1) {

					parent_table[v][j] = parent_table[parent_table[v][j - 1]][j - 1];
					wt_table[v][j] = wt_table[v][j - 1] + wt_table[parent_table[v][j - 1]][j - 1];

				} else {

					parent_table[v][j] = -1;
				}
			}
		}
	}

	big lift(int v, int dist) {

		if(dist == 0) {

			return 0;
		}

		int opt = logtable[dist];

		// fr(j, 0, maxjump) {

		// 	if((1 << j) > dist) {

		// 		break;
		// 	}

		// 	opt = j;
		// }

		return wt_table[v][opt] + lift(parent_table[v][opt], dist - (1 << opt));
	}
};

binlift b;


struct lca {

	int n, tl;
	vector<int> t;
	vector<int> first;
	vector<int> euler;
	vector<int> dv;

	void init(int N) {

		n = N;
		euler.clear();
		euler.reserve(2 * n);
		first.clear();
		first.resize(n);
		dv.clear();
		dv.resize(n);

		dv[0] = 0;
		dfs(0, 0);

		tl = euler.size();
		t.clear();
		t.resize(tl << 2, -1);
		build(1, 0, tl - 1);
	}

	int get_lca(int u, int v) {

		int l = first[u], r = first[v];
		if(l > r) swap(l, r);
		return query(1, 0, tl - 1, l, r);
	}

	void dfs(int node, int parent) {

		first[node] = euler.size();
		euler.push_back(node);

		for(int next : adj[node]) {

			if(next == parent) continue;

			dv[next] = dv[node] + 1;
			dfs(next, node);
			euler.push_back(node);
		}
	}

	int task(int child1, int child2) {

		if(child1 == -1) return child2;
		if(child2 == -1) return child1;

		if(dv[child1] < dv[child2]) {

			return child1;

		} else {

			return child2;
		}
	}

	void build(int node, int l, int r) {
	
		if(l == r) {
	
			t[node] = euler[l];
	
		} else {
	
			int mid = (l + r) >> 1;
			build(node << 1, l, mid);
			build((node << 1) + 1, mid + 1, r);
			t[node] = task(t[node << 1], t[(node << 1) + 1]);
		}
	}

	int query(int node, int l, int r, int lq, int rq) {
	
		if(lq > rq) {
	
			return -1;
	
		} else if(lq <= l && rq >= r) {
	
			return t[node];
	
		} else {
	
			int mid = (l + r) >> 1;
			return task(query(node << 1, l, mid, lq, min(rq, mid)), query((node << 1) + 1, mid + 1, r, max(lq, mid + 1), rq));
		}
	}
};

lca l;


big dist(int u, int v) {

	int LCA = l.get_lca(u, v);
	int d1 = l.dv[u] - l.dv[LCA];
	int d2 = l.dv[v] - l.dv[LCA];

	return b.lift(u, d1) + b.lift(v, d2);
}


struct centroid_decomposition {

	int n;
	vector<int> hidden;
	vector<int> parent;
	vector<int> subtree_size;
	vector<array<big, 2>> dp;
	vector<array<int, 2>> comes_from;

	void init(int N) {

		n = N;
		hidden.resize(n, 0);
		parent.resize(n, -1);
		subtree_size.resize(n, 0);
		dp.resize(n, {infinity, infinity});
		comes_from.resize(n, {-1, -1});
	}

	void decompose(int v, int p = -1) {

		get_size(v, -1);
		int centroid = get_centroid(v, -1, subtree_size[v]);
		hidden[centroid] = 1;
		parent[centroid] = p;

		for(int u : adj[centroid]) {

			if(hidden[u]) {

				continue;
			}

			decompose(u, centroid);
		}
	}

	int get_centroid(int v, int p, int sz) {

		for(int u : adj[v]) {

			if(hidden[u] || u == p) {

				continue;
			}

			if(subtree_size[u] * 2 > sz) {

				return get_centroid(u, v, sz);
			}
		}

		return v;
	}

	int get_size(int v, int p) {

		if(hidden[v]) return 0;

		int sz = 1;

		for(int u : adj[v]) {

			if(hidden[u] || u == p) {

				continue;
			}

			sz += get_size(u, v);
		}

		return subtree_size[v] = sz;
	}

	void shop(int v) {

		dp[v][1] = 0;
		comes_from[v][1] = v;

		if(dp[v][1] < dp[v][0]) {

			swap(dp[v][0], dp[v][1]);
			swap(comes_from[v][0], comes_from[v][1]);
		}

		int u = parent[v];
		int ch = v;

		while(u != -1) {

			big d = dist(u, v) + dp[v][0];

			if(d < dp[u][1]) {

				dp[u][1] = d;
				comes_from[u][1] = ch;

				if(dp[u][1] < dp[u][0]) {

					swap(dp[u][0], dp[u][1]);
					swap(comes_from[u][0], comes_from[u][1]);
				}
			}

			ch = u;
			u = parent[ch];
		}
	}

	void block(int v) {

		blocked[v] = 1;
		int u = parent[v];

		if(u == -1) {

			return;
		}

		if(comes_from[u][0] == v) {

			dp[u][0] = infinity;

		} else if(comes_from[u][1] == v) {

			dp[u][1] = infinity;
		}

		v = u;
		u = parent[v];

		while(u != -1) {

			if(comes_from[u][0] == v) {

				dp[u][0] = dist(u, v) + min(dp[v][0], dp[v][1]);

			} else if(comes_from[u][1] == v) {

				dp[u][1] = dist(u, v) + min(dp[v][0], dp[v][1]);
			}

			v = u;
			u = parent[v];
		}
	}

	void unblock(int v) {

		blocked[v] = 0;
		int u = parent[v];

		while(u != -1) {

			if(comes_from[u][0] == v) {

				dp[u][0] = dist(u, v) + min(dp[v][0], dp[v][1]);

			} else if(comes_from[u][1] == v) {

				dp[u][1] = dist(u, v) + min(dp[v][0], dp[v][1]);
			}

			v = u;
			u = parent[v];
		}
	}

	big query(int v) {

		big retval = min(dp[v][0], dp[v][1]);

		int u = parent[v];

		if(blocked[v]) {

			return retval;
		}

		while(u != -1) {

			retval = min(retval, dist(u, v) + min(dp[u][0], dp[u][1]));

			if(blocked[u]) {

				break;
			}

			u = parent[u];
		}

		return retval;
	}
};

centroid_decomposition g;


int start[maxn], fin[maxn];
vector<int> euler;
vector<array<int, 2>> edge_list;

void dfs(int v, int p) {

	start[v] = euler.size();
	euler.push_back(v);

	for(int u : adj[v]) {

		if(u == p) continue;

		b.add_node(u, v, edge_wt[u][v]);
		dfs(u, v);
	}

	fin[v] = euler.size() - 1;
}


void solve() {

	cin >> n_nodes >> n_shops >> nq >> destination;
	destination--;
	edge_list.reserve(n_nodes - 1);
	b.init(n_nodes, 20);

	fr(i, 0, n_nodes - 1) {

		int u, v, w;
		cin >> u >> v >> w;
		u--; v--;

		adj[u].push_back(v);
		adj[v].push_back(u);
		edge_list.push_back({u, v});
		edge_wt[u][v] = w;
		edge_wt[v][u] = w;
	}

	dfs(0, 0);
	b.build();

	fr(i, 0, n_nodes - 1) {

		int u = edge_list[i][0], v = edge_list[i][1];

		if(start[u] > start[v]) {

			swap(edge_list[i][0], edge_list[i][1]);
		}
	}

	l.init(n_nodes);
	g.init(n_nodes);
	g.decompose(0);

	fr(i, 0, n_shops) {

		int v;
		cin >> v;
		v--;
		g.shop(v);
	}

	fr(i, 0, nq) {

		int e, v;
		cin >> e >> v;
		e--; v--;

		int u = edge_list[e][1];

		if(start[v] >= start[u] && start[v] <= fin[u] && start[destination] >= start[u] && start[destination] <= fin[u]) {

			cout << "escaped\n";
			continue;
		}

		if((!(start[v] >= start[u] && start[v] <= fin[u])) && (!(start[destination] >= start[u] && start[destination] <= fin[u]))) {

			cout << "escaped\n";
			continue;
		}

		g.block(u);
		big r = g.query(v);
		g.unblock(u);

		if(r < infinity) {

			cout << r << nl;

		} else {

			cout << "oo\n";
		}
	}
}


int main() {
	
	speed;

	int q = 1;
	// cin >> q;

	while(q-- > 0) {

		solve();
	}

	return 0;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 27
• Subtask 3: 23 / 23
• Subtask 4: 0 / 41