제출 #1094629

#제출 시각아이디문제언어결과실행 시간메모리
1094629_8_8_Tourism (JOI23_tourism)C++17
18 / 100
197 ms30040 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5 + 12, MOD = (int)1e9 + 7; const int L = 19; vector<int> g[N]; int n, m, q, c[N], tin[N], tout[N], timer, s[N], head[N], ver[N]; int up[N][19], dep[N]; void bb(int v, int pr = -1) { s[v] = 1; for(int i = 0; i < (int)g[v].size(); i++) { int to = g[v][i]; if(to == pr) continue; bb(to, v); s[v] += s[to]; if(s[to] > s[g[v][0]] || g[v][0] == pr) { swap(g[v][i], g[v][0]); } } } void hld(int v, int pr = -1) { tin[v] = ++timer; ver[timer] = v; for(int to:g[v]) { if(to == pr) continue; if(to == g[v][0]) { head[to] = head[v]; } else { head[to] = to; } hld(to, v); } tout[v] = timer; } vector<pair<int,int>> qr[N]; void dfs(int v, int pr = 1) { up[v][0] = pr; for(int i = 1; i < L; ++i) { up[v][i] = up[up[v][i - 1]][i - 1]; } for(int to:g[v]) { if(to != pr) { dep[to] = dep[v] + 1; dfs(to, v); } } } bool is(int v, int u) { return (tin[v] <= tin[u] && tout[v] >= tout[u]); } int lca(int v, int u) { if(is(v, u)) return v; if(is(u, v)) return u; for(int i = L - 1; i >= 0; i--) { if(!is(up[v][i], u)) { v = up[v][i]; } } return up[v][0]; } pair<int, int> t[N * 4]; void build(int v = 1, int tl = 1, int tr = m - 1) { if(tl == tr) { int x = lca(c[tl], c[tl + 1]); // cout << c[tl] << ' ' << c[tl + 1] << ' ' << x << '\n'; t[v] = {dep[x], x}; } else { int tm = (tl + tr) >> 1; build(v + v, tl, tm); build(v + v + 1, tm + 1, tr); t[v] = min(t[v + v], t[v + v + 1]); } } const int inf = 1e9; pair<int, int> get(int l, int r, int v = 1, int tl = 1, int tr = m - 1) { if(l > r || tl > r || l > tr) return {inf, inf}; if(tl >= l && tr <= r) return t[v]; int tm = (tl + tr) >> 1; return min(get(l, r, v + v, tl, tm), get(l, r, v + v + 1, tm + 1, tr)); } int mn[N * 4], mod[N * 4], mx[N * 4]; void make(int v, int val) { mod[v] = mx[v] = mn[v] = val; } void push(int v) { if(mod[v]) { make(v + v, mod[v]); make(v + v + 1, mod[v]); mod[v] = 0; } } void upd(int l, int r, int val, int v = 1, int tl = 1, int tr = n) { if(l > r|| tl > r || l > tr) return; if(tl >= l && tr <= r) { make(v, val); } else { push(v); int tm = (tl + tr) >> 1; upd(l, r, val, v + v, tl, tm); upd(l, r, val, v + v + 1, tm + 1, tr); mx[v] = max(mx[v + v], mx[v + v + 1]); mn[v] = min(mn[v + v], mn[v + v + 1]); } } int find(int val, int v = 1, int tl = 1, int tr = n) { if(mn[v] >= val) { return (tr - tl + 1); } if(mx[v] < val) { return 0; } push(v); int tm = (tl + tr) >> 1; return find(val,v + v, tl, tm) + find(val, v + v + 1, tm + 1, tr); } void nv(int v, int i) { while(v != 1) { upd(tin[head[v]], tin[v], i); // cout << tin[head[v]] << ' ' << tin[v] << '\n'; v = up[head[v]][0]; } } int res[N]; void out(int v = 1, int tl = 1, int tr = n) { if(tl == tr) { // cout << mx[v] << " "; } else { push(v); int tm = (tl + tr) >> 1; out(v + v, tl, tm); out(v + v + 1, tm + 1, tr); } } void test() { cin >> n >> m >> q; for(int i = 1; i <= n - 1; i++) { int a, b; cin >> a >> b; g[a].push_back(b); g[b].push_back(a); } for(int i = 1; i <= m; i++) { cin >> c[i]; } dep[1] = 1; bb(1); head[1] = 1; hld(1); dfs(1); build(); for(int i = 1; i <= q; i++) { int l, r; cin >> l >> r; if(l == r) { res[i] = 1; continue; } qr[r].push_back({l, i}); } for(int i = 1; i <= m; i++) { nv(c[i], i); if(i == 3) { // out(); // cout << find(1) << '\n'; // return; } for(auto [l, id]:qr[i]) { int x = get(l, i - 1).second; // cout << x << '\n'; res[id] = find(l) - dep[x] + 1; } } for(int i = 1; i <= q; i++) { cout << res[i] << '\n'; } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); int t = 1; // cin >> t; while(t--) test(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...