Submission #1091042

#TimeUsernameProblemLanguageResultExecution timeMemory
1091042underwaterkillerwhaleTourism (JOI23_tourism)C++17
28 / 100
5091 ms64084 KiB
#include <bits/stdc++.h> #define ll long long #define pii pair<int,int> #define pll pair<ll,ll> #define rep(i,m,n) for(int i=(m); i<=(n); i++) #define reb(i,m,n) for(int i=(m); i>=(n); i--) #define iter(id, v) for(auto id : v) #define fs first #define se second #define MP make_pair #define pb push_back #define bit(msk, i) ((msk >> i) & 1) #define SZ(v) (ll)v.size() #define ALL(v) v.begin(),v.end() using namespace std; mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count()); ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); } const int N = 1e5 + 7; const int Mod = 1e9 + 2022; ///loonf mod sai const int INF = 1e9; const ll BASE = 137; const int szBL = 320; struct Query { int fs, se, id; }; int n, m, Q; vector<int> ke[N]; Query qr[N]; int C[N]; int high[N], szC[N], euler[2 * N], posin[N], pa[N], ein[N], eout[N]; pii flca[2 * N][25]; void pdfs (int u, int p) { static int sz = 0, time_dfs = 0; high[u] = high[p] + 1; pa[u] = p; szC[u] = 1; flca[++sz][0] = MP(high[u], u); posin[u] = sz; ein[u] = ++time_dfs; iter (&v, ke[u]) { if (v != p) { pdfs(v, u); szC[u] += szC[v]; flca[++sz][0] = MP(high[u], u); } } eout[u] = time_dfs; } void init_LCA () { for (int j = 1; (1 << j) <= 2 * n; ++j) for (int i = 1; i + (1 << j) - 1 <= 2 * n; ++i) flca[i][j] = min(flca[i][j - 1], flca[i + (1 << j - 1)][j - 1]); } int LCA (int u, int v) { u = posin[u]; v = posin[v]; if (u > v) swap(u, v); int K = 31 - __builtin_clz(v - u + 1); return min(flca[u][K], flca[v - (1 << K) + 1][K]).se; } namespace sub2 { int pre[N]; void dfs (int u, int p, int &res) { iter (&v, ke[u]) { if (v != p) { dfs(v, u, res); pre[u] += pre[v]; } } if (pre[u] > 0) ++res; } void solution () { rep (q, 1, Q) { rep (i, 1, n) pre[i] = 0; int L = qr[q].fs, R = qr[q].se; int Lca = C[L]; rep (i, L, R) { Lca = LCA(Lca, C[i]); } rep (i, L, R) { pre[C[i]]++; pre[pa[Lca]]--; } int res = 0; dfs(1, 0, res); cout << res <<"\n"; } } } namespace sub6 { int sptLCA[N][25]; int res = 0; int ptrL = 1, ptrR = 0; multiset<pii> S; void update (int u, int val) { pii cur = MP(ein[u], u); if (val == -1) { // assert(S.find(cur) != S.end()); S.erase(S.find(cur)); } int lc = -1, rc = -1; auto it = S.lower_bound(cur); if (it != S.end()) rc = it->se; if (it != S.begin()) lc = prev(it)->se; if (rc == -1 && lc == -1) res += val * high[u]; else { int nearest = 1; if (rc != -1) { nearest = LCA(u, rc); } if (lc != -1) { int v = LCA(u, lc); if (high[nearest] < high[v]) nearest = v; } res += val * (high[u] - high[nearest]); // cout << u <<" "<<lc <<","<<rc<<" "<<res<<","<<val<<"\n"; } if (val == 1) S.insert(cur); // cout << ptrL <<" "<<ptrR<<" "<<val<<":\n"; // iter (&id, S) cout << id.se<<" "; // cout<<"\n"; } void shifting (int L, int R) { while (ptrL > L) { --ptrL; update(C[ptrL], 1); } while (ptrR < R) { ++ptrR; update (C[ptrR], 1); } while (ptrL < L) { update(C[ptrL], -1); ++ptrL; } while (ptrR > R) { update (C[ptrR], -1); --ptrR; } } void solution () { sort (qr + 1, qr + 1 + Q, [] (Query A, Query B) { if (A.fs / szBL != B.fs / szBL) return A.fs < B.fs; else if (!((A.fs / szBL) &1)) return A.se < B.se; else return A.se > B.se; }); rep (i, 1, m) sptLCA[i][0] = C[i]; for (int j = 1; (1 << j) <= m; ++j) for (int i = 1; i + (1 << j) - 1 <= m; ++i) sptLCA[i][j] = LCA(sptLCA[i][j - 1], sptLCA[i + (1 << j - 1)][j - 1]); auto get_LCA = [] (int L, int R) { int K = 31 - __builtin_clz(R - L + 1); return LCA(sptLCA[L][K], sptLCA[R - (1 << K) + 1][K]); }; vector<int> Ans(Q + 1); rep (q, 1, Q) { int L = qr[q].fs, R = qr[q].se, id = qr[q].id; shifting(L, R); Ans[id] = res - high[get_LCA(L, R)] + 1; // cout << id<<":"<<Ans[id] <<","<<get_LCA(L, R)<<"\n"; } rep (i, 1, Q) cout << Ans[i] <<"\n"; } } void solution() { cin >> n >> m >> Q; rep (i, 1, n - 1) { int u, v; cin >> u >> v; ke[u].pb(v); ke[v].pb(u); } rep (i, 1, m) cin >> C[i]; rep (i, 1, Q) cin >> qr[i].fs >> qr[i].se, qr[i].id = i; pdfs(1, 0); init_LCA(); // if (n <= 2000 && m <= 2000 && Q <= 2000) sub2 :: solution(); // else sub6 :: solution(); } #define file(name) freopen(name".inp","r",stdin); \ freopen(name".out","w",stdout); int main () { // file("c"); // ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0); int num_Test = 1; // cin >> num_Test; while (num_Test--) solution(); } /* no bug +8 chu y break hay return se lam hong logic xet transition cua i va i + 1 construct ket qua chu y truong hop : KHONG CO GI ko làm được hướng 1: đổi hướng làm hướng 2: đưa ra nhận xét tim mo hinh bai toan sau khi doc de trung ten bien trong ham gan nhat co the dan den sai 10 7 3 6 5 3 6 9 3 8 3 7 8 7 1 2 5 7 10 8 4 9 4 10 1 10 7 6 4 4 1 3 6 7 */

Compilation message (stderr)

tourism.cpp: In function 'void init_LCA()':
tourism.cpp:61:63: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   61 |             flca[i][j] = min(flca[i][j - 1], flca[i + (1 << j - 1)][j - 1]);
      |                                                             ~~^~~
tourism.cpp: In function 'void sub6::solution()':
tourism.cpp:174:69: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  174 |             sptLCA[i][j] = LCA(sptLCA[i][j - 1], sptLCA[i + (1 << j - 1)][j - 1]);
      |                                                                   ~~^~~
#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...