이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#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<vpi>
const ll oo = (ll)1e18 + 5;
const int T = 8e5 + 5;
const int N = 1e5 + 5;
int n, s, q, e, p[N], tin[N], tout[N], s1[N], c[N], timer = 0, root = 0;
int h[N], tr[T], ans[N], query[N];
matrix pre[N], suf[N], seg[N];
vpi edge, adj[N], a[N], a1[N];
vi vertex, adj1[N];
map<int, int> dis[N];
void upd(int i, int l, int r, int q, int 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]);
}
int 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(vpi &a, vpi &b) { // by tin
int l = 0;
vpi ans;
EACH(i, a) {
WHILE(l < sz(b) && tin[b[l].st] < tin[i.st]) ans.pb(b[l++]);
ans.pb(i);
}
WHILE(l < sz(b)) ans.pb(b[l++]);
a = ans;
}
void merge1(vpi &a, vpi &b) { // by tout
int l = 0;
vpi ans;
EACH(i, a) {
WHILE(l < sz(b) && tout[b[l].st] < tout[i.st]) 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, 0});
a1[ct].pb({ct, 0});
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;
vpi &an = a[nxt], &a1n = a1[nxt];
merge(a[ct], an);
merge1(a1[ct], a1n);
adj1[ct].pb(nxt);
}
EACH(i, a[ct]) i.nd = dis[ct][i.st];
EACH(i, a1[ct]) i.nd = dis[ct][i.st];
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].st] < 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].st] > 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].st] <= 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, -1});
if (ans2 != -1) suf[u][ans2].pb({id, -1});
}
if (p[u]) add(i, R, p[u], id);
}
void process(int u) {
int m = sz(a[u]);
int Min = oo;
FOS(i, m - 1, 0) {
int cur = a1[u][i].st;
if (cur == e) Min = min(Min, -oo);
else if (c[cur]) Min = min(Min, a1[u][i].nd);
EACH(j, suf[u][i]) {
int v = j.st;
ans[v] = min(ans[v], dis[u][query[v]] + Min);
}
}
Min = oo;
FOR(i, 0, m - 1) {
int cur = a[u][i].st;
if (cur == e) Min = min(Min, -oo);
else if (c[cur]) Min = min(Min, a[u][i].nd);
EACH(j, pre[u][i]) {
int v = j.st;
ans[v] = min(ans[v], dis[u][query[v]] + Min);
}
}
FOR(i, 0, m - 1) {
int cur = a1[u][i].st;
if (cur == e) upd(1, 1, 2 * n, tin[cur], -oo);
else if (c[cur]) upd(1, 1, 2 * n, tin[cur], a1[u][i].nd);
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].st;
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
----------------------------------------------------------------
*/
컴파일 시 표준 에러 (stderr) 메시지
valley.cpp: In function 'void dfs(long long int, long long int)':
valley.cpp:37:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
37 | #define EACH(i, x) for (auto &(i) : (x))
| ^
valley.cpp:81:2: note: in expansion of macro 'EACH'
81 | EACH(j, adj[u]) {
| ^~~~
valley.cpp: In function 'void dfs1(long long int, long long int)':
valley.cpp:37:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
37 | #define EACH(i, x) for (auto &(i) : (x))
| ^
valley.cpp:95:2: note: in expansion of macro 'EACH'
95 | EACH(j, adj[u]) {
| ^~~~
valley.cpp: In function 'void dfs2(long long int, long long int)':
valley.cpp:37:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
37 | #define EACH(i, x) for (auto &(i) : (x))
| ^
valley.cpp:104:2: note: in expansion of macro 'EACH'
104 | EACH(j, adj[u]) {
| ^~~~
valley.cpp: In function 'long long int fct(long long int, long long int, long long int)':
valley.cpp:37:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
37 | #define EACH(i, x) for (auto &(i) : (x))
| ^
valley.cpp:112:2: note: in expansion of macro 'EACH'
112 | EACH(j, adj[u]) {
| ^~~~
valley.cpp: In function 'void merge(vpi&, vpi&)':
valley.cpp:37:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
37 | #define EACH(i, x) for (auto &(i) : (x))
| ^
valley.cpp:122:2: note: in expansion of macro 'EACH'
122 | EACH(i, a) {
| ^~~~
valley.cpp: In function 'void merge1(vpi&, vpi&)':
valley.cpp:37:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
37 | #define EACH(i, x) for (auto &(i) : (x))
| ^
valley.cpp:132:2: note: in expansion of macro 'EACH'
132 | EACH(i, a) {
| ^~~~
valley.cpp: In function 'long long int centroid(long long int)':
valley.cpp:37:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
37 | #define EACH(i, x) for (auto &(i) : (x))
| ^
valley.cpp:148:2: note: in expansion of macro 'EACH'
148 | EACH(i, vertex) dis[ct][i] = h[i];
| ^~~~
valley.cpp:37:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
37 | #define EACH(i, x) for (auto &(i) : (x))
| ^
valley.cpp:149:2: note: in expansion of macro 'EACH'
149 | EACH(j, adj[ct]) {
| ^~~~
valley.cpp:37:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
37 | #define EACH(i, x) for (auto &(i) : (x))
| ^
valley.cpp:159:2: note: in expansion of macro 'EACH'
159 | EACH(i, a[ct]) i.nd = dis[ct][i.st];
| ^~~~
valley.cpp:37:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
37 | #define EACH(i, x) for (auto &(i) : (x))
| ^
valley.cpp:160:2: note: in expansion of macro 'EACH'
160 | EACH(i, a1[ct]) i.nd = dis[ct][i.st];
| ^~~~
valley.cpp: In function 'void process(long long int)':
valley.cpp:34:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
34 | #define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
| ^
valley.cpp:208:2: note: in expansion of macro 'FOS'
208 | FOS(i, m - 1, 0) {
| ^~~
valley.cpp:37:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
37 | #define EACH(i, x) for (auto &(i) : (x))
| ^
valley.cpp:212:3: note: in expansion of macro 'EACH'
212 | EACH(j, suf[u][i]) {
| ^~~~
valley.cpp:33:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
33 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
valley.cpp:218:2: note: in expansion of macro 'FOR'
218 | FOR(i, 0, m - 1) {
| ^~~
valley.cpp:37:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
37 | #define EACH(i, x) for (auto &(i) : (x))
| ^
valley.cpp:222:3: note: in expansion of macro 'EACH'
222 | EACH(j, pre[u][i]) {
| ^~~~
valley.cpp:33:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
33 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
valley.cpp:227:2: note: in expansion of macro 'FOR'
227 | FOR(i, 0, m - 1) {
| ^~~
valley.cpp:37:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
37 | #define EACH(i, x) for (auto &(i) : (x))
| ^
valley.cpp:231:3: note: in expansion of macro 'EACH'
231 | EACH(j, seg[u][i]) {
| ^~~~
valley.cpp:33:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
33 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
valley.cpp:236:2: note: in expansion of macro 'FOR'
236 | FOR(i, 0, m - 1) {
| ^~~
valley.cpp:37:31: warning: unnecessary parentheses in declaration of 'v' [-Wparentheses]
37 | #define EACH(i, x) for (auto &(i) : (x))
| ^
valley.cpp:240:2: note: in expansion of macro 'EACH'
240 | EACH(v, adj1[u]) process(v);
| ^~~~
valley.cpp: In function 'int main()':
valley.cpp:33:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
33 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
valley.cpp:247:5: note: in expansion of macro 'FOR'
247 | FOR(i, 1, n << 3) tr[i] = oo;
| ^~~
valley.cpp:33:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
33 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
valley.cpp:249:5: note: in expansion of macro 'FOR'
249 | FOR(i, 1, n - 1) {
| ^~~
valley.cpp:33:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
33 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
valley.cpp:259:5: note: in expansion of macro 'FOR'
259 | FOR(i, 1, s) {
| ^~~
valley.cpp:33:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
33 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
valley.cpp:264:5: note: in expansion of macro 'FOR'
264 | FOR(j, 1, q) {
| ^~~
valley.cpp:33:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
33 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
valley.cpp:272:5: note: in expansion of macro 'FOR'
272 | FOR(i, 1, q)
| ^~~| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
