oj.uz

답안 #646774

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
646774 2022-09-30T15:26:27 Z ghostwriter Valley (BOI19_valley) C++14
36 / 100
 3000 ms 228736 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
#ifdef LOCAL
#include <debug.h>
#else
#define debug(...)
#endif
#define ft front
#define bk back
#define st first
#define nd second
#define ins insert
#define ers erase
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define mtp make_tuple
#define bg begin
#define ed end
#define all(x) (x).bg(), (x).ed()
#define sz(x) (int)(x).size()
// #define int long long
typedef long long ll; typedef unsigned long long ull;
typedef double db; typedef long double ldb;
typedef pair<int, int> pi; typedef pair<ll, ll> pll;
typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll;
typedef string str;
template<typename T> T gcd(T a, T b) { return (b == 0? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
#define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
#define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
#define FSN(i, n) for (int (i) = (n) - 1; (i) >= 0; --(i))
#define EACH(i, x) for (auto &(i) : (x))
#define WHILE while
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
/*
----------------------------------------------------------------
    END OF TEMPLATE
----------------------------------------------------------------
    Tran The Bao - ghostwriter
    Training for VOI23 gold medal
----------------------------------------------------------------
    DIT ME TTB NON
----------------------------------------------------------------
*/
#define matrix vector<vi>
#define matrix1 vector<vpi>
const ll oo = (ll)1e18 + 5;
const int T = 8e5 + 1;
const int N = 1e5 + 1;
int n, s, q, e, p[N], tin[N], tout[N], s1[N], c[N], query[N], timer = 0, root = 0;
ll h[N], tr[T], ans[N];
matrix pre[N], suf[N];
matrix1 seg[N];
vpi edge, adj[N];
vi a[N], a1[N], vertex, adj1[N];
map<pi, ll> dis;
void upd(int i, int l, int r, int q, ll v) {
	if (r < q || l > q) return;
	if (l == r) {
		tr[i] = v;
		return;
	}
	int mid = l + (r - l) / 2;
	upd(i * 2, l, mid, q, v);
	upd(i * 2 + 1, mid + 1, r, q, v);
	tr[i] = min(tr[i * 2], tr[i * 2 + 1]);
}
ll get(int i, int l, int r, int ql, int qr) {
	if (r < ql || l > qr) return oo;
	if (ql <= l && r <= qr) return tr[i];
	int mid = l + (r - l) / 2;
	return min(get(i * 2, l, mid, ql, qr), get(i * 2 + 1, mid + 1, r, ql, qr));
}
void dfs(int u, int p) {
	tin[u] = ++timer;
	EACH(j, adj[u]) {
		int v = j.st;
		if (v == p) continue;
		dfs(v, u);
	}
	tout[u] = ++timer;
}
bool isc(int a, int b) { return tin[a] >= tin[b] && tout[b] >= tout[a]; }
int getp(pi a) {
	if (isc(a.st, a.nd)) return a.st;
	return a.nd;
}
void dfs1(int u, int p) {
	s1[u] = 1;
	EACH(j, adj[u]) {
		int v = j.st;
		if (c[v] || v == p) continue;
		dfs1(v, u);
		s1[u] += s1[v];
	}
}
void dfs2(int u, int p) {
	vertex.pb(u);
	EACH(j, adj[u]) {
		int v = j.st, w = j.nd;
		if (c[v] || v == p) continue;
		h[v] = h[u] + w;
		dfs2(v, u);
	}
}
int fct(int u, int p, int total) {
	EACH(j, adj[u]) {
		int v = j.st; 
		if (c[v] || v == p) continue;
		if (s1[v] > total / 2) return fct(v, u, total);
	}
	return u;
}
void merge(vi &a, vi &b) { // by tin
	int l = 0;
	vi ans;
	EACH(i, a) {
		WHILE(l < sz(b) && tin[b[l]] < tin[i]) ans.pb(b[l++]);
		ans.pb(i);
	}
	WHILE(l < sz(b)) ans.pb(b[l++]);
	a = ans;
}
void merge1(vi &a, vi &b) { // by tout
	int l = 0;
	vi ans;
	EACH(i, a) {
		WHILE(l < sz(b) && tout[b[l]] < tout[i]) ans.pb(b[l++]);
		ans.pb(i);
	}
	WHILE(l < sz(b)) ans.pb(b[l++]);
	a = ans;
}
int centroid(int u) {
	dfs1(u, 0);
	int ct = fct(u, 0, s1[u]);
	c[ct] = 1;
	a[ct].pb(ct);
	a1[ct].pb(ct);
	vertex.clear();
	h[ct] = 0;
	dfs2(ct, 0);
	EACH(i, vertex) dis[{ct, i}] = h[i];
	EACH(j, adj[ct]) {
		int v = j.st;
		if (c[v]) continue;
		int nxt = centroid(v);
		p[nxt] = ct;
		vi &an = a[nxt], &a1n = a1[nxt];
		merge(a[ct], an);
		merge1(a1[ct], a1n);
		adj1[ct].pb(nxt);
	}
	int m = sz(a[ct]);
	pre[ct].resize(m);
	suf[ct].resize(m);
	seg[ct].resize(m);
	return ct;
}
void add(int i, int R, int u, int id) {
	int m = sz(a[u]);
	int l = 0, r = m - 1, ans1 = -1, ans2 = -1, ans3 = -1;
	WHILE(l <= r) {
		int mid = l + (r - l) / 2;
		if (tin[a[u][mid]] < tin[i]) {
			ans1 = mid;
			l = mid + 1;
		}
		else r = mid - 1;
	}
	l = 0; r = m - 1;
	WHILE(l <= r) {
		int mid = l + (r - l) / 2;
		if (tout[a1[u][mid]] > tout[i]) {
			ans2 = mid;
			r = mid - 1;
		}
		else l = mid + 1;
	}
	l = 0; r = m - 1;
	WHILE(l <= r) {
		int mid = l + (r - l) / 2;
		if (tout[a1[u][mid]] <= tout[i]) {
			ans3 = mid;
			l = mid + 1;
		}
		else r = mid - 1;
	}
	if (isc(R, i)) {
		if (ans3 != -1) seg[u][ans3].pb({id, tin[i]});
	}
	else {
		if (ans1 != -1) pre[u][ans1].pb(id);
		if (ans2 != -1) suf[u][ans2].pb(id);
	}
	if (p[u]) add(i, R, p[u], id);
}
void process(int u) {
	int m = sz(a[u]);
	ll Min = oo;
	FOS(i, m - 1, 0) {
		int cur = a1[u][i];
		if (cur == e) Min = min(Min, -oo);
		else if (c[cur]) Min = min(Min, dis[{u, cur}]);
		EACH(v, suf[u][i]) ans[v] = min(ans[v], dis[{u, query[v]}] + Min);
	}
	Min = oo;
	FOR(i, 0, m - 1) {
		int cur = a[u][i];
		if (cur == e) Min = min(Min, -oo);
		else if (c[cur]) Min = min(Min, dis[{u, cur}]);
		EACH(v, pre[u][i]) ans[v] = min(ans[v], dis[{u, query[v]}] + Min);
	}
	FOR(i, 0, m - 1) {
		int cur = a1[u][i];
		if (cur == e) upd(1, 1, 2 * n, tin[cur], -oo);
		else if (c[cur]) upd(1, 1, 2 * n, tin[cur], dis[{u, cur}]);
		EACH(j, seg[u][i]) {
			int v = j.st, t = j.nd;
			ans[v] = min(ans[v], dis[{u, query[v]}] + get(1, 1, 2 * n, t, 2 * n));
		}
	}
	FOR(i, 0, m - 1) {
		int cur = a1[u][i];
		upd(1, 1, 2 * n, tin[cur], oo);
	}
	EACH(v, adj1[u]) process(v);
}
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    // freopen(file".inp", "r", stdin);
    // freopen(file".out", "w", stdout);
    cin >> n >> s >> q >> e;
    FOR(i, 1, n << 3) tr[i] = oo;
    edge.pb({0, 0});
    FOR(i, 1, n - 1) {
    	int u, v, w;
    	cin >> u >> v >> w;
    	edge.pb({u, v});
    	adj[u].pb({v, w});
    	adj[v].pb({u, w});
    }
    dfs(1, 0);
    root = centroid(1);
    memset(c, 0, sizeof c);
    FOR(i, 1, s) {
    	int ci;
    	cin >> ci;
    	c[ci] = 1;
    }
    FOR(j, 1, q) {
    	ans[j] = oo;
    	int i, r;
    	cin >> i >> r;
    	add(getp(edge[i]), r, r, j);
    	query[j] = r;
    }
    process(root);
    FOR(i, 1, q)
    	if (ans[i] < 0) cout << "escaped\n";
    	else if (ans[i] < oo) cout << ans[i] << '\n';
    	else cout << "oo\n";
    return 0;
}
/*
5 2 3 1
1 2 3
1 3 2
3 4 1
3 5 2
2
4
2 2
2 5
4 5
----------------------------------------------------------------
From Benq:
    stuff you should look for
        * int overflow, array bounds
        * special cases (n=1?)
        * do smth instead of nothing and stay organized
        * WRITE STUFF DOWN
        * DON'T GET STUCK ON ONE APPROACH
----------------------------------------------------------------
*/

Compilation message

valley.cpp: In function 'void dfs(int, int)':
valley.cpp:39:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   39 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
valley.cpp:85:2: note: in expansion of macro 'EACH'
   85 |  EACH(j, adj[u]) {
      |  ^~~~
valley.cpp: In function 'void dfs1(int, int)':
valley.cpp:39:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   39 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
valley.cpp:99:2: note: in expansion of macro 'EACH'
   99 |  EACH(j, adj[u]) {
      |  ^~~~
valley.cpp: In function 'void dfs2(int, int)':
valley.cpp:39:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   39 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
valley.cpp:108:2: note: in expansion of macro 'EACH'
  108 |  EACH(j, adj[u]) {
      |  ^~~~
valley.cpp: In function 'int fct(int, int, int)':
valley.cpp:39:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   39 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
valley.cpp:116:2: note: in expansion of macro 'EACH'
  116 |  EACH(j, adj[u]) {
      |  ^~~~
valley.cpp: In function 'void merge(vi&, vi&)':
valley.cpp:39:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   39 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
valley.cpp:126:2: note: in expansion of macro 'EACH'
  126 |  EACH(i, a) {
      |  ^~~~
valley.cpp: In function 'void merge1(vi&, vi&)':
valley.cpp:39:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   39 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
valley.cpp:136:2: note: in expansion of macro 'EACH'
  136 |  EACH(i, a) {
      |  ^~~~
valley.cpp: In function 'int centroid(int)':
valley.cpp:39:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   39 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
valley.cpp:152:2: note: in expansion of macro 'EACH'
  152 |  EACH(i, vertex) dis[{ct, i}] = h[i];
      |  ^~~~
valley.cpp:39:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   39 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
valley.cpp:153:2: note: in expansion of macro 'EACH'
  153 |  EACH(j, adj[ct]) {
      |  ^~~~
valley.cpp: In function 'void process(int)':
valley.cpp:36:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   36 | #define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
      |                               ^
valley.cpp:210:2: note: in expansion of macro 'FOS'
  210 |  FOS(i, m - 1, 0) {
      |  ^~~
valley.cpp:39:31: warning: unnecessary parentheses in declaration of 'v' [-Wparentheses]
   39 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
valley.cpp:214:3: note: in expansion of macro 'EACH'
  214 |   EACH(v, suf[u][i]) ans[v] = min(ans[v], dis[{u, query[v]}] + Min);
      |   ^~~~
valley.cpp:35:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   35 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
valley.cpp:217:2: note: in expansion of macro 'FOR'
  217 |  FOR(i, 0, m - 1) {
      |  ^~~
valley.cpp:39:31: warning: unnecessary parentheses in declaration of 'v' [-Wparentheses]
   39 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
valley.cpp:221:3: note: in expansion of macro 'EACH'
  221 |   EACH(v, pre[u][i]) ans[v] = min(ans[v], dis[{u, query[v]}] + Min);
      |   ^~~~
valley.cpp:35:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   35 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
valley.cpp:223:2: note: in expansion of macro 'FOR'
  223 |  FOR(i, 0, m - 1) {
      |  ^~~
valley.cpp:39:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   39 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
valley.cpp:227:3: note: in expansion of macro 'EACH'
  227 |   EACH(j, seg[u][i]) {
      |   ^~~~
valley.cpp:35:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   35 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
valley.cpp:232:2: note: in expansion of macro 'FOR'
  232 |  FOR(i, 0, m - 1) {
      |  ^~~
valley.cpp:39:31: warning: unnecessary parentheses in declaration of 'v' [-Wparentheses]
   39 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
valley.cpp:236:2: note: in expansion of macro 'EACH'
  236 |  EACH(v, adj1[u]) process(v);
      |  ^~~~
valley.cpp: In function 'int main()':
valley.cpp:35:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   35 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
valley.cpp:243:5: note: in expansion of macro 'FOR'
  243 |     FOR(i, 1, n << 3) tr[i] = oo;
      |     ^~~
valley.cpp:35:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   35 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
valley.cpp:245:5: note: in expansion of macro 'FOR'
  245 |     FOR(i, 1, n - 1) {
      |     ^~~
valley.cpp:35:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   35 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
valley.cpp:255:5: note: in expansion of macro 'FOR'
  255 |     FOR(i, 1, s) {
      |     ^~~
valley.cpp:35:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   35 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
valley.cpp:260:5: note: in expansion of macro 'FOR'
  260 |     FOR(j, 1, q) {
      |     ^~~
valley.cpp:35:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   35 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
valley.cpp:268:5: note: in expansion of macro 'FOR'
  268 |     FOR(i, 1, q)
      |     ^~~

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 18096 KB Output is correct
2 Correct 19 ms 18188 KB Output is correct
3 Correct 20 ms 18152 KB Output is correct
4 Correct 20 ms 18076 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 18096 KB Output is correct
2 Correct 19 ms 18188 KB Output is correct
3 Correct 20 ms 18152 KB Output is correct
4 Correct 20 ms 18076 KB Output is correct
5 Correct 14 ms 18004 KB Output is correct
6 Correct 16 ms 18388 KB Output is correct
7 Correct 18 ms 18516 KB Output is correct
8 Correct 13 ms 18004 KB Output is correct
9 Correct 15 ms 18384 KB Output is correct
10 Correct 15 ms 18608 KB Output is correct
11 Correct 16 ms 18004 KB Output is correct
12 Correct 17 ms 18288 KB Output is correct
13 Correct 18 ms 18600 KB Output is correct
14 Correct 16 ms 18508 KB Output is correct

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1690 ms 124268 KB Output is correct
2 Correct 2437 ms 187264 KB Output is correct
3 Execution timed out 3019 ms 228736 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 18096 KB Output is correct
2 Correct 19 ms 18188 KB Output is correct
3 Correct 20 ms 18152 KB Output is correct
4 Correct 20 ms 18076 KB Output is correct
5 Correct 14 ms 18004 KB Output is correct
6 Correct 16 ms 18388 KB Output is correct
7 Correct 18 ms 18516 KB Output is correct
8 Correct 13 ms 18004 KB Output is correct
9 Correct 15 ms 18384 KB Output is correct
10 Correct 15 ms 18608 KB Output is correct
11 Correct 16 ms 18004 KB Output is correct
12 Correct 17 ms 18288 KB Output is correct
13 Correct 18 ms 18600 KB Output is correct
14 Correct 16 ms 18508 KB Output is correct
15 Correct 1690 ms 124268 KB Output is correct
16 Correct 2437 ms 187264 KB Output is correct
17 Execution timed out 3019 ms 228736 KB Time limit exceeded
18 Halted 0 ms 0 KB -