oj.uz

답안 #452680

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
452680 2021-08-04T05:35:40 Z naman1601 Valley (BOI19_valley) C++17
100 / 100
 334 ms 44740 KB 
/*
++[---------->+<]>.-[------>+<]>-.++++++++.+++++.-[->+++++<]>-.-[--->++<]>--.+.[--->+<]>---.[->+++<]>++.++++++.-------.++++++.--[--->+<]>.-[->+++<]>-..+++++++++++++.[----->++<]>.------------.+[----->+<]>.--------.+++++++++++++.-------------.--[--->+<]>-.---[->++++<]>-.++++[->+++<]>.--[--->+<]>-.[->+++<]>++.-.+++.---.-[->+++<]>.-[--->++<]>+.++++.------.[--->+<]>---.+[----->+<]>.------------.+++++++.-------.--[--->+<]>---.+++[->+++<]>++..+++++++++.---------.-[->+++<]>.+[----->+<]>+.-------------.+++++++.+.----[->+++<]>-.
*/
#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 = 3000000000000000000;
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];
big attribute[maxn];
vector<array<int, 2>> edges;
map<int, int> ew[maxn];


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[destination] = 0;
		dfs(destination, destination);

		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;


struct hld_t {

	int tl;
	vector<big> t;

	void init(int l, big val) {

		tl = l;
		t = vector<big>(tl << 2, val);
	}

	big task(big child1, big child2) {
	
		return min(child1, child2);
	}
	
	void update(int node, int l, int r, int pos, big val) {
	
		if(l == r) {
	
			t[node] = val;
	
		} else {
	
			int mid = (l + r) >> 1;
	
			if(pos <= mid) {
	
				update(node << 1, l, mid, pos, val);
	
			} else {
	
				update((node << 1) + 1, mid + 1, r, pos, val);
			}
	
			t[node] = task(t[node << 1], t[(node << 1) + 1]);
		}
	}

	void update(int pos, big val) {

		update(1, 0, tl - 1, pos, val);
	}
	
	big query(int node, int l, int r, int lq, int rq) {
	
		if(lq > rq) {
	
			return infinity;
	
		} 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));
		}
	}

	big query(int lq, int rq) {

		return query(1, 0, tl - 1, lq, rq);
	}
	
	void build(vector<int>& v, int node, int l, int r) {
	
		if(l == r) {
	
			t[node] = attribute[v[l]];

			// replace attribute with appropriate variable
	
		} else {
	
			int mid = (l + r) >> 1;
			build(v, node << 1, l, mid);
			build(v, (node << 1) + 1, mid + 1, r);
			t[node] = task(t[node << 1], t[(node << 1) + 1]);
		}
	}

	void build(vector<int>& v) {

		build(v, 1, 0, tl - 1);
	}
};


struct hld {

	int n;
	vector<int> hld_path;
	vector<int> pos;
	vector<int> heavy_of;
	vector<int> head_of;
	vector<int> parent_of;

	hld_t t;

	void init(int N) {

		n = N;

		hld_path.clear();
		hld_path.reserve(n);
		pos.clear();
		pos.resize(n);
		heavy_of.clear();
		heavy_of.resize(n, -1);
		head_of.clear();
		head_of.resize(n);
		parent_of.clear();
		parent_of.resize(n);

		t.init(n, infinity);

		parent_of[destination] = destination;
		dfs(destination);
		head_of[destination] = destination;
		decompose(destination);

		t.build(hld_path);
	}

	int dfs(int node) {

		int subtree_size = 1;
		int current_heavy_size = -1;

		for(int next : adj[node]) {

			if(next == parent_of[node]) continue;

			parent_of[next] = node;
			int next_size = dfs(next);
			subtree_size += next_size;

			if(next_size > current_heavy_size) {

				current_heavy_size = next_size;
				heavy_of[node] = next;
			}
		}

		return subtree_size;
	}

	void decompose(int node) {

		pos[node] = hld_path.size();
		hld_path.push_back(node);

		if(heavy_of[node] != -1) {

			head_of[heavy_of[node]] = head_of[node];
			decompose(heavy_of[node]);
		}

		for(int next : adj[node]) {

			if(next == heavy_of[node] || next == parent_of[node]) continue;

			head_of[next] = next;
			decompose(next);
		}
	}

	big task(big v1, big v2) {

		return min(v1, v2);
	}

	big query(int node, int ancestor) {

		big retval = infinity;

		for(; head_of[node] != head_of[ancestor]; node = parent_of[head_of[node]]) {

			retval = task(retval, t.query(pos[head_of[node]], pos[node]));
		}

		retval = task(retval, t.query(pos[ancestor], pos[node]));
		return retval;
	}

	void update(int node, big value) {

		t.update(pos[node], value);
	}
};

hld h;


big dp[maxn], dep[maxn];
int start[maxn], fin[maxn];
vector<int> euler;


void init(int v, int p, big d) {

	dep[v] = d;

	for(int u : adj[v]) {

		if(u == p) continue;

		init(u, v, d + ew[u][v]);
	}
}

void dfs(int v, int p) {

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

	for(int u : adj[v]) {

		if(u == p) continue;

		dfs(u, v);
		dp[v] = min(dp[v], ew[u][v] + dp[u]);
	}

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


void solve() {

	cin >> n_nodes >> n_shops >> nq >> destination;
	destination--;

	fr(i, 0, n_nodes) dp[i] = infinity;
	edges.reserve(n_nodes - 1);

	fr(i, 0, n_nodes - 1)  {

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

		ew[u][v] = w;
		ew[v][u] = w;
		adj[u].push_back(v);
		adj[v].push_back(u);
		edges.push_back({u, v});
	}

	init(destination, destination, 0);

	fr(i, 0, n_shops) {

		int v;
		cin >> v;
		v--;
		dp[v] = 0;
	}

	dfs(destination, destination);

	fr(i, 0, n_nodes - 1) {

		if(start[edges[i][0]] > start[edges[i][1]]) {

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


	// L.init(n_nodes);
	h.init(n_nodes);

	fr(i, 0, nq) {

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

		int u = edges[e][1];
		// cout << "i: " << u << nl;

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

			big r = dep[v] + h.query(v, u);

			if(r < infinity) {

				cout << r << nl;

			} else {

				cout << "oo\n";
			}

		} else {

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


int main() {
	
	speed;

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

	while(q-- > 0) {

		solve();
	}

	return 0;
}

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7500 KB Output is correct
2 Correct 8 ms 7500 KB Output is correct
3 Correct 8 ms 7500 KB Output is correct
4 Correct 7 ms 7512 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7500 KB Output is correct
2 Correct 8 ms 7500 KB Output is correct
3 Correct 8 ms 7500 KB Output is correct
4 Correct 7 ms 7512 KB Output is correct
5 Correct 7 ms 7628 KB Output is correct
6 Correct 7 ms 7628 KB Output is correct
7 Correct 6 ms 7636 KB Output is correct
8 Correct 7 ms 7628 KB Output is correct
9 Correct 7 ms 7628 KB Output is correct
10 Correct 6 ms 7628 KB Output is correct
11 Correct 7 ms 7648 KB Output is correct
12 Correct 6 ms 7640 KB Output is correct
13 Correct 7 ms 7628 KB Output is correct
14 Correct 7 ms 7636 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 298 ms 34128 KB Output is correct
2 Correct 333 ms 33864 KB Output is correct
3 Correct 323 ms 33840 KB Output is correct
4 Correct 334 ms 38236 KB Output is correct
5 Correct 303 ms 38120 KB Output is correct
6 Correct 330 ms 43500 KB Output is correct

Subtask #4
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7500 KB Output is correct
2 Correct 8 ms 7500 KB Output is correct
3 Correct 8 ms 7500 KB Output is correct
4 Correct 7 ms 7512 KB Output is correct
5 Correct 7 ms 7628 KB Output is correct
6 Correct 7 ms 7628 KB Output is correct
7 Correct 6 ms 7636 KB Output is correct
8 Correct 7 ms 7628 KB Output is correct
9 Correct 7 ms 7628 KB Output is correct
10 Correct 6 ms 7628 KB Output is correct
11 Correct 7 ms 7648 KB Output is correct
12 Correct 6 ms 7640 KB Output is correct
13 Correct 7 ms 7628 KB Output is correct
14 Correct 7 ms 7636 KB Output is correct
15 Correct 298 ms 34128 KB Output is correct
16 Correct 333 ms 33864 KB Output is correct
17 Correct 323 ms 33840 KB Output is correct
18 Correct 334 ms 38236 KB Output is correct
19 Correct 303 ms 38120 KB Output is correct
20 Correct 330 ms 43500 KB Output is correct
21 Correct 304 ms 33576 KB Output is correct
22 Correct 296 ms 33368 KB Output is correct
23 Correct 302 ms 33248 KB Output is correct
24 Correct 311 ms 38300 KB Output is correct
25 Correct 297 ms 44740 KB Output is correct
26 Correct 256 ms 33632 KB Output is correct
27 Correct 280 ms 33300 KB Output is correct
28 Correct 299 ms 33332 KB Output is correct
29 Correct 298 ms 36500 KB Output is correct
30 Correct 308 ms 39928 KB Output is correct
31 Correct 281 ms 33576 KB Output is correct
32 Correct 293 ms 33416 KB Output is correct
33 Correct 301 ms 33548 KB Output is correct
34 Correct 316 ms 37880 KB Output is correct
35 Correct 306 ms 44604 KB Output is correct
36 Correct 302 ms 37964 KB Output is correct