제출 #410549

#제출 시각아이디문제언어결과실행 시간메모리
410549PurpleCrayonČVENK (COI15_cvenk)C++17
38 / 100
3090 ms521092 KiB
#include "bits/stdc++.h" using namespace std; #define sz(v) int(v.size()) #define ar array typedef long long ll; const int MAXN = 2e5+10, MOD = 1e9+7, MAXL = 34; const int INF = 1e9+10; map<ar<ll, 2>, int> idx; vector<ar<ll, 2>> anc[MAXN*2]; int lsb(ll x){ return 1+__builtin_ctzll(x); } ll dep(ar<ll, 2> c){ return c[0]+c[1]; } ar<ll, 2> par(ar<ll, 2> c) { if (!c[0] || !c[1]) { return {max(0ll, c[0]-1), max(0ll, c[1]-1)}; } if (lsb(c[0]) < lsb(c[1])) return {c[0]-1, c[1]}; else return {c[0], c[1]-1}; } ar<ll, 2> jmp(ar<ll, 2> c, ll d) { if (!d) return c; ll v = d; ll lb = c[0]&(-c[0]), rb = c[1]&(-c[1]); if (c[0]) v = min(v, lb); if (c[1]) v = min(v, rb); if (!c[1]) return jmp({c[0]-v, c[1]}, d-v); if (!c[0]) return jmp({c[0], c[1]-v}, d-v); if (lb < rb) return jmp({c[0]-v, c[1]}, d-v); else return jmp({c[0], c[1]-v}, d-v); } ar<ll, 2> binjmp(ar<ll, 2> c, int d) { if (idx.count(c)) return anc[idx[c]][d]; int i = sz(idx); idx[c] = i; anc[i].resize(MAXL); for (int j = 0; j < MAXL; j++) anc[i][j] = jmp(c, 1ll<<j); return anc[i][d]; } ar<ll, 2> fast_lca(ar<ll, 2> a, ar<ll, 2> b) { if (dep(a) < dep(b)) swap(a, b); a = jmp(a, dep(a)-dep(b)); if (a == b) return a; //cerr << a[0] << ' ' << a[1] << endl; for (ll k = 40; k >= 0; k--) { ll cur = 1ll<<k; if (dep(a) >= cur && dep(b) >= cur) { ar<ll, 2> na = binjmp(a, k), nb = binjmp(b, k); if (na != nb) { a = na, b = nb; } } } return par(a); } ar<ll, 2> lca(ar<ll, 2> a, ar<ll, 2> b) { if (dep(a) < dep(b)) swap(a, b); a = jmp(a, dep(a)-dep(b)); if (a == b) return a; //cerr << a[0] << ' ' << a[1] << endl; for (ll k = MAXL-1; k >= 0; k--) { ll cur = 1ll<<k; if (dep(a) >= cur && dep(b) >= cur) { ar<ll, 2> na = jmp(a, cur), nb = jmp(b, cur); if (na != nb) { a = na, b = nb; } } } return par(a); } ar<ll, 2> lca_slow(ar<ll, 2> a, ar<ll, 2> b) { while (a != b) { if (dep(a) < dep(b)) swap(a, b); a = par(a); } return a; } ll dist(ar<ll, 2> a, ar<ll, 2> b) { return dep(a)+dep(b)-2*dep(lca(a, b)); } bool comp(ar<ll, 2> a, ar<ll, 2> b) { if (a == b) return 0; ar<ll, 2> l = fast_lca(a, b); if (a == l) return 1; if (b == l) return 0; ll k1 = dep(a)-dep(l)-1, k2 = dep(b)-dep(l)-1; ar<ll, 2> a1 = jmp(a, k1), a2 = jmp(b, k2); return a1 < a2; } int n; ar<ll, 2> gen() { ll a = ll(rand())|(ll(rand())<<15); ll b = 0; for (int i = 0; i < 30; i++) { if ((a>>i)&1^1) { b |= (rand()&1)<<i; } } assert((a&b) == 0); //cerr << a << ' ' << b << endl; return {a, b}; } vector<int> sub; vector<vector<int>> adj; int dfs(int c=0, int p=-1) { for (auto nxt : adj[c]) if (nxt != p) sub[c] += dfs(nxt, c); return sub[c]; } int dfsAns(int c=0, int p=-1) { for (auto nxt : adj[c]) if (nxt != p) { int val = sub[nxt] - (sub[0] - sub[nxt]); if (val > 0) return dfsAns(nxt, c); } return c; } int solve_tree(vector<ar<int, 2>> ed, vector<int> cost) { sub = cost; adj.resize(sz(cost)); for (auto e : ed) adj[e[0]].push_back(e[1]), adj[e[1]].push_back(e[0]); dfs(); return dfsAns(); } void solve(){ cin >> n; srand(time(0)); vector<ar<ll, 2>> a(n), b; for (int i = 0; i < n; i++) { cin >> a[i][0] >> a[i][1]; //a[i] = gen(); } b = a; sort(a.begin(), a.end(), comp); set<ar<ll, 2>> s; for (int i = 0; i < n-1; i++) { a.push_back(fast_lca(a[i], a[i+1])); } sort(a.begin(), a.end(), comp); a.erase(unique(a.begin(), a.end()), a.end()); map<ar<ll, 2>, int> mp; for (int i = 0; i < sz(a); i++) mp[a[i]] = i; vector<int> cost(sz(a)); for (int i = 0; i < n; i++) cost[mp[b[i]]]++; vector<ar<int, 2>> ed; for (int i = 0; i < sz(a)-1; i++) { auto v1 = a[i], v2 = a[i+1]; ed.push_back({mp[fast_lca(v1, v2)], mp[v2]}); } int ROOT = solve_tree(ed, cost); auto c = a[ROOT]; ll ans = 0; for (int i = 0; i < n; i++) ans += dist(c, b[i]); cout << ans << '\n'; } int main(){ ios::sync_with_stdio(false); cin.tie(0); int T=1; //cin >> T; while (T--) solve(); }

컴파일 시 표준 에러 (stderr) 메시지

cvenk.cpp: In function 'std::array<long long int, 2> gen()':
cvenk.cpp:103:19: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
  103 |         if ((a>>i)&1^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...