Submission #1124567

#TimeUsernameProblemLanguageResultExecution timeMemory
1124567macneilTourism (JOI23_tourism)C++20
18 / 100
592 ms39404 KiB
#include <iostream> #include <vector> #include <cmath> #include <algorithm> #include <string> #include <bitset> #include <iterator> #include <iomanip> #include <map> #include <set> #include <unordered_map> #include <unordered_set> #include <ctime> #include <deque> #include <queue> #include <stack> #include <random> #include <cassert> using namespace std; #define int long long #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() typedef long long ll; typedef long double ld; struct SegTree { vector<int> szs; vector<pair<int, int>> tr; vector<int> lol; int sz; SegTree(){} void build(int n) { sz = (1 << ((int)log2(n))) * 2; lol.resize(2 * sz, -1); tr.resize(sz * 2, {1e9, 1e9}); szs.resize(sz * 2); for (int i = 0; i < n; ++i) szs[sz - 1 + i] = 1; for (int i = sz - 2; i >= 0; --i) szs[i] = szs[i * 2 + 1] + szs[i * 2 + 2]; } void push(int v) { if (lol[v] == -1) return; tr[v] = {lol[v], lol[v]}; if (2 * v + 2 < 2 * sz) { lol[2 * v + 1] = lol[v]; lol[2 * v + 2] = lol[v]; } lol[v] = -1; } pair<int, int> merge(pair<int, int> a, pair<int, int> b) { return {min(a.first, b.first), max(a.second, b.second)}; } void update(int v, int l, int r, int ql, int qr, int x) { push(v); if (ql >= r || qr <= l) return; if (l >= ql && r <= qr) { lol[v] = x; push(v); return; } int m = (l + r) / 2; update(2 * v + 1, l, m, ql, qr, x); update(2 * v + 2, m, r, ql, qr, x); tr[v] = merge(tr[2 * v + 1], tr[2 * v + 2]); } void update(int l, int r, int x) { update(0, 0, sz, l, r, x); } int get(int v, int l, int r, int x) { push(v); if (tr[v].first >= x) return 0; if (tr[v].second < x) return r - l; if (r - l == 0) return 0; int m = (l + r) / 2; return get(v * 2 + 1, l, m, x) + get(v * 2 + 2, m, r, x); } int get(int x) { return get(0, 0, sz, x); } }; vector<int> sz, upto, tin, tout, ord, backord; vector<vector<int>> p, gr; SegTree lol; int timer = 0; void dfssize(int v, int pr) { p[0][v] = pr; for (int i = 1; i < 20; ++i) p[i][v] = p[i - 1][p[i - 1][v]]; tin[v] = timer++; sz[v] = 1; for (auto e : gr[v]) { if (e == pr) continue; dfssize(e, v); sz[v] += sz[e]; } tout[v] = timer++; } void dfsreorder(int v, int pr) { backord[v] = ord.size(); ord.push_back(v); if (upto[v] == -1) upto[v] = v; if (gr[v].size() == 1 && pr != -1) return; if (gr[v][0] == pr) swap(gr[v][0], gr[v][1]); for (auto &e : gr[v]) { if (e == pr) continue; if (sz[e] > sz[gr[v][0]]) swap(e, gr[v][0]); } upto[gr[v][0]] = upto[v]; for (auto e : gr[v]) { if (e == pr) continue; dfsreorder(e, v); } } bool isanc(int a, int b) { return tin[a] <= tin[b] && tout[a] >= tout[b]; } int lca(int a, int b) { if (isanc(a, b)) return a; if (isanc(b, a)) return b; for (int i = 19; i >= 0; --i) { if (!isanc(p[i][a], b)) a = p[i][a]; } return p[0][a]; } void update(int a, int b, int ind) { int c = lca(a, b); while (1) { int t = upto[a]; if (isanc(t, c)) t = c; lol.update(backord[t], backord[a] + 1, ind); if (t == c) break; a = p[0][t]; } while (1) { int t = upto[b]; if (isanc(t, c)) t = c; lol.update(backord[t], backord[b] + 1, ind); if (t == c) break; b = p[0][t]; } } int get(int x) { return lol.get(x); } void solve() { int n, m, q; cin >> n >> m >> q; upto.resize(n, -1); sz.resize(n); tin.resize(n); tout.resize(n); backord.resize(n); p.resize(20, vector<int>(n)); gr.resize(n); lol.build(n); for (int i = 0; i < n - 1; ++i) { int a, b; cin >> a >> b; --a; --b; gr[a].push_back(b); gr[b].push_back(a); } dfssize(0, 0); dfsreorder(0, -1); vector<int> lolkek(m); for (int i = 0; i < m; ++i) { cin >> lolkek[i]; lolkek[i]--; } vector<int> ans(q); vector<vector<pair<int, int>>> qs(m); for (int i = 0; i < q; ++i) { int l, r; cin >> l >> r; if (l == r) { ans[i] = 1; continue; } qs[l - 1].push_back({r, i}); } for (int i = m - 2; i >= 0; --i) { update(lolkek[i], lolkek[i + 1], i + 1); for (auto e : qs[i]) { ans[e.second] = get(e.first); } } for (auto e : ans) cout << e << '\n'; } signed main() { int tc = 1; #ifdef LOCAL freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #else ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #endif // int g; cin >> g; // cin >> tc; for (int t = 1; t <= tc; t++) { // cout << "Case #" << t << ": "; solve(); } }
#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...