| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1294969 | Davdav1232 | The Potion of Great Power (CEOI20_potion) | C++20 | 0 ms | 0 KiB |
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,bmi,bmi2")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAX_N = 100000 + 5;
int H[MAX_N];
int N;
int D;
int d = 300; // block size; can tune (e.g. 300..700)
struct Snapshot {
int day; // time of snapshot (the last update index included)
vector<int> items; // neighbors present at this snapshot (no order assumptions)
};
vector<vector<Snapshot>> changes; // per-node snapshots (starts with one empty snapshot)
vector<vector<pair<int,int>>> upd; // per-node updates: pair<time, neighbor>
static int markStamp[MAX_N]; // global marks (timestamping)
static int globalStamp = 1;
// initialize arrays and structures
inline void init(int NN, int DD, int HH[]) {
N = NN;
D = DD;
for (int i = 0; i < N; ++i) H[i] = HH[i];
changes.assign(N, vector<Snapshot>());
upd.assign(N, vector<pair<int,int>>());
for (int i = 0; i < N; ++i) {
changes[i].push_back(Snapshot{0, vector<int>()});
}
// reset global stamping
++globalStamp;
if (globalStamp > (1<<30)) { // safety wrap (unlikely)
memset(markStamp, 0, sizeof(markStamp));
globalStamp = 1;
}
}
// add UU pairwise updates described by arrays AA[], BB[] (1-based times implied in original)
inline void curseChanges(int UU, int AA[], int BB[]) {
// append updates to adjacency update lists
for (int i = 0; i < UU; ++i) {
int a = AA[i];
int b = BB[i];
int t = i + 1; // time index as in original code
upd[a].push_back({t, b});
upd[b].push_back({t, a});
}
// build block snapshots for each node
for (int node = 0; node < N; ++node) {
int usize = (int)upd[node].size();
if (usize == 0) continue;
// reserve approx number of snapshots
int expected_blocks = (usize + d - 1) / d;
changes[node].reserve(max(1, (int)changes[node].size() + expected_blocks + 2));
// for each full block of size d, create snapshot
for (int r = d; r <= usize; r += d) {
const Snapshot &prev = changes[node].back();
// build new snapshot by toggling the block [r-d, r-1] on top of prev.items
++globalStamp; // unique stamp for this construction
int stamp = globalStamp;
vector<int> touched;
touched.reserve((int)prev.items.size() + d);
// mark all prev items as present with stamp
for (int v : prev.items) {
markStamp[v] = stamp;
touched.push_back(v);
}
// apply toggles from updates in this block
for (int j = r - d; j < r; ++j) {
int u = upd[node][j].second;
if (markStamp[u] == stamp) {
// currently present -> toggle off: set to stamp-1 (absent)
markStamp[u] = stamp - 1;
// it's already in touched
} else {
// not present -> toggle on
if (markStamp[u] != stamp - 1) { // first time we touch this element during this construction
touched.push_back(u);
}
markStamp[u] = stamp;
}
}
// collect present items into new vector
vector<int> newItems;
newItems.reserve(touched.size());
for (int v : touched) {
if (markStamp[v] == stamp) newItems.push_back(v);
}
// push snapshot with the time of last update in that block
int lastTime = upd[node][r - 1].first;
changes[node].push_back(Snapshot{lastTime, std::move(newItems)});
}
}
}
// returns the list of neighbors of node p after applying all updates with time <= day
// complexity: O(size(snapshot) + number of partial updates applied)
inline vector<int> query(int p, int day) {
const auto &snapVec = changes[p];
int r = 0;
for (int i = 0, sz = (int)snapVec.size(); i < sz; ++i) {
if (snapVec[i].day <= day) r = i;
else break;
}
// start from snapshot r
const vector<int> &base = snapVec[r].items;
int usize = (int)upd[p].size();
int startIdx = r * d;
++globalStamp;
int stamp = globalStamp;
vector<int> touched;
touched.reserve((int)base.size() + min(d, usize - startIdx));
// mark base snapshot items as present
for (int v : base) {
markStamp[v] = stamp;
touched.push_back(v);
}
// apply partial toggles from startIdx up to day
for (int t = startIdx; t < usize && upd[p][t].first <= day; ++t) {
int u = upd[p][t].second;
if (markStamp[u] == stamp) {
// present -> toggle off
markStamp[u] = stamp - 1;
// u is already in touched (either from base or previous toggle)
} else {
// not present -> toggle on
if (markStamp[u] != stamp - 1) touched.push_back(u);
markStamp[u] = stamp;
}
}
// collect items that are present
vector<int> ans;
ans.reserve(touched.size());
for (int v : touched) {
if (markStamp[v] == stamp) ans.push_back(v);
}
return ans;
}
// compute minimal difference between H values in neighbors of x and y at time v
inline int question(int x, int y, int v) {
vector<int> ans1 = query(x, v);
vector<int> ans2 = query(y, v);
if (ans1.empty() || ans2.empty()) return (int)1e9;
vector<ll> h1; h1.reserve(ans1.size());
vector<ll> h2; h2.reserve(ans2.size() + 2);
for (int r : ans1) h1.push_back(H[r]);
for (int r : ans2) h2.push_back(H[r]);
// sentinels
h2.push_back((ll)-1000000000);
h2.push_back((ll)2000000000);
sort(h1.begin(), h1.end());
sort(h2.begin(), h2.end());
ll m = (ll)4e18;
// two-pointer-like approach
int e = 0;
for (int i = 0, n1 = (int)h1.size(); i < n1; ++i) {
// advance e while next sentinel/value is < h1[i]
while (e + 1 < (int)h2.size() && h2[e + 1] < h1[i]) ++e;
// compare with nearest below and above
if (e < (int)h2.size()) m = min(m, llabs(h1[i] - h2[e]));
if (e + 1 < (int)h2.size()) m = min(m, llabs(h2[e + 1] - h1[i]));
}
if (m > (ll)2e9) return (int)1e9;
return (int)m;
}