oj.uz

답안 #646260

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
646260 2022-09-29T10:38:08 Z ymm Valley (BOI19_valley) C++17
100 / 100
 867 ms 23892 KB 
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 100'010;
vector<pii> query[N];
int lower_v[N];
vector<pii> A[N];
ll w[N];
double near_m_height_st[N];
double near_child[N];
double height[N];
int st[N], ft[N];
bool has_shop[N];
ll ans[N];
int n, q, cnt_shops, rt;

void dfs1(int v, int p, int &t, double h)
{
	st[v] = t++;
	height[v] = h;
	for (auto [u, e] : A[v]) {
		if (u == p)
			continue;
		lower_v[e] = u;
		dfs1(u, v, t, h + w[e]);
	}
	ft[v] = t;
}

__attribute__((optimize("O3,unroll-loops"),target("avx")))
void update(int l, int r, double x)
{
	Loop (i,l,r) {
		near_m_height_st[i] = near_m_height_st[i] < x?
		                      near_m_height_st[i]: x;
	}
}

void up_near(int v, int p)
{
	near_child[v] = has_shop[v]? 0: 1e100;
	for (auto [u, e] : A[v]) {
		if (u == p)
			continue;
		near_child[v] = min(near_child[v], near_child[u] + w[e]);
	}
	update(st[v], ft[v], near_child[v] - height[v]);
}

void ans_queries(int v)
{
	for (auto [i, u] : query[v]) {
		if (st[u] < st[v] || ft[v] <= st[u])
			ans[i] = -2;
		else if (near_m_height_st[st[u]] > 1e20)
			ans[i] = -1;
		else
			ans[i] = near_m_height_st[st[u]] + height[u];
	}
}

void dfs2(int v, int p)
{
	for (auto [u, e] : A[v]) {
		if (u != p)
			dfs2(u, v);
	}
	up_near(v, p);
	ans_queries(v);
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> cnt_shops >> q >> rt; --rt;
	Loop (i,0,n-1) {
		int v, u;
		cin >> v >> u >> w[i];
		--v; --u;
		A[v].push_back({u, i});
		A[u].push_back({v, i});
	}
	dfs1(rt, -1, *new int(0), 0);
	Loop (i,0,cnt_shops) {
		int v;
		cin >> v;
		has_shop[v-1] = 1;
	}
	Loop (i,0,q) {
		int e, v;
		cin >> e >> v;
		--e; --v;
		query[lower_v[e]].push_back({i, v});
	}
	fill(near_m_height_st, near_m_height_st+N, 1e100);
	dfs2(rt, -1);
	Loop (i,0,q) {
		switch (ans[i]) {
		case -2: cout << "escaped\n"; break;
		case -1: cout << "oo\n"; break;
		default: cout << ans[i] << '\n'; break;
		}
	}
}

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 6100 KB Output is correct
2 Correct 5 ms 6100 KB Output is correct
3 Correct 5 ms 6188 KB Output is correct
4 Correct 5 ms 6168 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 6100 KB Output is correct
2 Correct 5 ms 6100 KB Output is correct
3 Correct 5 ms 6188 KB Output is correct
4 Correct 5 ms 6168 KB Output is correct
5 Correct 4 ms 5984 KB Output is correct
6 Correct 4 ms 5856 KB Output is correct
7 Correct 4 ms 5936 KB Output is correct
8 Correct 6 ms 5972 KB Output is correct
9 Correct 4 ms 5856 KB Output is correct
10 Correct 5 ms 5932 KB Output is correct
11 Correct 4 ms 5972 KB Output is correct
12 Correct 4 ms 5936 KB Output is correct
13 Correct 4 ms 5972 KB Output is correct
14 Correct 4 ms 5940 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 116 ms 18892 KB Output is correct
2 Correct 126 ms 18496 KB Output is correct
3 Correct 157 ms 18480 KB Output is correct
4 Correct 311 ms 20268 KB Output is correct
5 Correct 329 ms 19860 KB Output is correct
6 Correct 867 ms 21580 KB Output is correct

Subtask #4
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 6100 KB Output is correct
2 Correct 5 ms 6100 KB Output is correct
3 Correct 5 ms 6188 KB Output is correct
4 Correct 5 ms 6168 KB Output is correct
5 Correct 4 ms 5984 KB Output is correct
6 Correct 4 ms 5856 KB Output is correct
7 Correct 4 ms 5936 KB Output is correct
8 Correct 6 ms 5972 KB Output is correct
9 Correct 4 ms 5856 KB Output is correct
10 Correct 5 ms 5932 KB Output is correct
11 Correct 4 ms 5972 KB Output is correct
12 Correct 4 ms 5936 KB Output is correct
13 Correct 4 ms 5972 KB Output is correct
14 Correct 4 ms 5940 KB Output is correct
15 Correct 116 ms 18892 KB Output is correct
16 Correct 126 ms 18496 KB Output is correct
17 Correct 157 ms 18480 KB Output is correct
18 Correct 311 ms 20268 KB Output is correct
19 Correct 329 ms 19860 KB Output is correct
20 Correct 867 ms 21580 KB Output is correct
21 Correct 108 ms 20080 KB Output is correct
22 Correct 115 ms 19736 KB Output is correct
23 Correct 122 ms 19660 KB Output is correct
24 Correct 382 ms 21684 KB Output is correct
25 Correct 795 ms 23892 KB Output is correct
26 Correct 127 ms 20176 KB Output is correct
27 Correct 125 ms 19840 KB Output is correct
28 Correct 128 ms 19840 KB Output is correct
29 Correct 369 ms 21124 KB Output is correct
30 Correct 669 ms 21848 KB Output is correct
31 Correct 119 ms 20188 KB Output is correct
32 Correct 117 ms 19876 KB Output is correct
33 Correct 145 ms 19976 KB Output is correct
34 Correct 681 ms 21624 KB Output is correct
35 Correct 771 ms 23820 KB Output is correct
36 Correct 785 ms 21704 KB Output is correct