Submission #986924

#TimeUsernameProblemLanguageResultExecution timeMemory
986924876polTourism (JOI23_tourism)C++17
28 / 100
5048 ms78688 KiB
#ifndef LOCAL #pragma GCC optimize("Ofast") #pragma GCC target("avx2") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define dbg(...) #define STRUCT_DBG(...) #else #include "lib/debug.h" #endif using namespace std; using namespace __gnu_pbds; using ll = long long; using ld = long double; using pll = pair<ll, ll>; template <class T> using vec = vector<T>; using vll = vector<ll>; using vpll = vector<pair<ll, ll>>; using vvll = vector<vector<ll>>; using vvpll = vector<vector<pair<ll, ll>>>; template <class T> using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define FOR(i, s, e) for (ll i = (ll)s; i < (ll)e; i++) #define CFOR(i, s, e) for (ll i = (ll)s; i <= (ll)e; i++) #define RFOR(i, e, s) for (ll i = (ll)e - 1; i >= (ll)s; i--) #define TRAV(a, c) for (const auto &a : c) #define all(x) x.begin(), x.end() #define MOD 1000000007 // #define MOD 998244353 #define FASTIO #define PRECISION // #define FILE "file" #define SINGLE // #define MULTIPLE // #define GOOGLE void solve() { ll n, m, q; cin >> n >> m >> q; vvll graph(n + 1); FOR(i, 0, n - 1) { ll a, b; cin >> a >> b; graph[a].push_back(b); graph[b].push_back(a); } vll euler, dist, tin(n + 1), level(n + 1); ll cdist = 0; function<void(ll, ll)> dfs1 = [&](ll curr, ll prev) { tin[curr] = euler.size(); level[curr] = cdist; euler.push_back(curr); dist.push_back(cdist); cdist++; TRAV(e, graph[curr]) { if (e == prev) continue; dfs1(e, curr); euler.push_back(curr); dist.push_back(cdist - 1); } cdist--; }; dfs1(1, 0); ll L = 20; vvpll st(L, vpll(euler.size())); FOR(i, 0, euler.size()) st[0][i] = {dist[i], euler[i]}; FOR(i, 1, L) { CFOR(j, 0, euler.size() - (1ll << i)) { st[i][j] = min(st[i - 1][j], st[i - 1][j + (1ll << (i - 1))]); } } auto lca = [&](ll x, ll y) { x = tin[x]; y = tin[y]; if (x > y) swap(x, y); ll q = 63 - __builtin_clzll(y - x + 1); return min(st[q][x], st[q][y - (1ll << q) + 1]).second; }; auto ds = [&](ll x, ll y) { return level[x] + level[y] - 2 * level[lca(x, y)]; }; vll c(m + 1); CFOR(i, 1, m) cin >> c[i]; FOR(_, 0, q) { ll l, r; cin >> l >> r; vll nodes; nodes.reserve(r - l + 2); ll root = c[l]; CFOR(i, l, r) { nodes.push_back(c[i]); root = lca(root, c[i]); } nodes.push_back(root); sort(all(nodes)); nodes.erase(unique(all(nodes)), nodes.end()); sort(all(nodes), [&](ll o1, ll o2) { return tin[o1] < tin[o2]; }); vll stk = {root}; ll ans = 1; for (auto it = nodes.begin() + 1; it != nodes.end(); it++) { vll tr; while (lca(stk.back(), *it) != stk.back()) { tr.push_back(stk.back()); stk.pop_back(); } if (tr.size() && stk.back() != lca(*it, tr.back())) { stk.push_back(lca(*it, tr.back())); } FOR(i, 0, tr.size() - 1) { ans += ds(tr[i], tr[i + 1]); } if (tr.size()) ans += ds(tr.back(), stk.back()); stk.push_back(*it); } FOR(i, 0, stk.size() - 1) { ans += ds(stk[i], stk[i + 1]); } cout << ans << "\n"; // vll cc; // cc.reserve(edges.size() * 2); // TRAV(e, edges) { // cc.push_back(e.first); // cc.push_back(e.second); // } // sort(all(cc)); // cc.erase(unique(all(cc)), cc.end()); // vvpll cgraph(cc.size()); // ll ans = 0; // TRAV(e, edges) { // ll u = lower_bound(all(cc), e.first) - cc.begin(); // ll v = lower_bound(all(cc), e.second) - cc.begin(); // ll d = ds(e.first, e.second); // cgraph[u].push_back({v, d}); // cgraph[v].push_back({u, d}); // ans += d - 1; // } // function<pll(ll, ll)> dfs2 = [&](ll curr, ll prev) -> pll { // pll best = {0, curr}; // TRAV(e, cgraph[curr]) { // if (e.first == prev) continue; // pll obj = dfs2(e.first, curr); // obj.first += e.second; // best = max(best, obj); // } // return best; // }; // pll o1 = dfs2(0, -1); // pll o2 = dfs2(o1.second, -1); // cout << ans - o2.first << "\n"; // cout << ans + cc.size() << "\n"; } } int main() { #ifdef FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); #endif #ifdef PRECISION cout << fixed << setprecision(10); cerr << fixed << setprecision(10); #endif #ifdef FILE freopen((FILE + string(".in")).c_str(), "r", stdin); freopen((FILE + string(".out")).c_str(), "w", stdout); #endif #ifdef SINGLE solve(); #endif #ifdef MULTIPLE ll t; cin >> t; for (ll i = 1; i <= t; i++) { solve(); } #endif #ifdef GOOGLE ll t; cin >> t; for (ll i = 1; i <= t; i++) { cout << "Case #" << i << ": "; solve(); } #endif }
#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...