Submission #959411

#TimeUsernameProblemLanguageResultExecution timeMemory
959411Yang8onBall Machine (BOI13_ballmachine)C++14
100 / 100
515 ms25516 KiB
#include <bits/stdc++.h> #define Y8o "Ball Machine" #define maxn 100005 #define ll long long #define pii pair<int, int> #define gb(i, j) ((i >> j) & 1) using namespace std; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); ll GetRandom(ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rng); } void iof() { if(fopen(Y8o".inp", "r")) { freopen(Y8o".inp", "r", stdin); freopen(Y8o".out", "w", stdout); } ios_base::sync_with_stdio(0); cin.tie(NULL), cout.tie(NULL); } void ctime() { cerr << "\n" << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n"; } int n, Q, root, cnt; int Min[maxn], cha[maxn][18], h[maxn], pos[maxn], a[maxn]; vector<int> o[maxn]; void dfs(int u) { for(int v : o[u]) { h[v] = h[u] + 1, cha[v][0] = u; for(int j = 1; j <= 17; j ++) cha[v][j] = cha[cha[v][j - 1]][j - 1]; dfs(v); Min[u] = min({ Min[u], Min[v] }); } Min[u] = min(Min[u], u); } void dfs2(int u) { for(int v : o[u]) dfs2(v); a[++ cnt] = u; pos[u] = cnt; } struct dl { int val, lazy; } st[4 * maxn]; void build(int id = 1, int l = 1, int r = n) { if(l == r) { st[id] = {0, -1}; return; } int mid = (l + r) >> 1; build(id * 2, l, mid); build(id * 2 + 1, mid + 1, r); st[id].val = st[id * 2].val + st[id * 2 + 1].val; st[id].lazy = -1; } void down(int id, int l, int r) { int t = st[id].lazy; if(t == -1) return ; int mid = (l + r) >> 1; st[id * 2] = {t * (mid - l + 1), t}; st[id * 2 + 1] = {t * (r - mid), t}; st[id].lazy = -1; } void update(int u, int v, int val, int id = 1, int l = 1, int r = n) { if(v < l || r < u) return ; if(u <= l && r <= v) { st[id] = {val * (r - l + 1), val}; return ; } down(id, l, r); int mid = (l + r) >> 1; update(u, v, val, id * 2, l, mid); update(u, v, val, id * 2 + 1, mid + 1, r); st[id].val = st[id * 2].val + st[id * 2 + 1].val; } int get(int u, int v, int id = 1, int l = 1, int r = n) { if(v < l || r < u) return 0; if(u <= l && r <= v) return st[id].val; down(id, l, r); int mid = (l + r) >> 1; return get(u, v, id * 2, l, mid) + get(u, v, id * 2 + 1, mid + 1, r); } int add(int x) { int l = 1, r = n; while(l <= r) { int mid = (l + r) >> 1; if(get(1, mid) + x <= mid) r = mid - 1; else l = mid + 1; } update(1, l, 1); return a[l]; } int jump(int u, int len) { for(int i = 0; i <= 17; i ++) if(gb(len, i)) u = cha[u][i]; return u; } int erase_(int u) { int l = 1, r = n; while(l <= r) { int mid = (l + r) >> 1, v = jump(u, mid); if(v != 0 && get(pos[v], pos[v]) == 1) l = mid + 1; else r = mid - 1; } int par = jump(u, r); update(pos[par], pos[par], 0); return h[u] - h[par]; } int dd[maxn]; void solve() { cin >> n >> Q; for(int i = 1, v; i <= n; i ++) { cin >> v; if(v == 0) root = i; else o[v].push_back(i); } memset(Min, 0x3f, sizeof Min); dfs(root); for(int i = 1; i <= n; i ++) if(o[i].size()) sort(o[i].begin(), o[i].end(), [](int x, int y) { return Min[x] < Min[y]; }); dfs2(root); build(); for(int i = 1, id, u; i <= Q; i ++) { cin >> id >> u; if(id == 1) cout << add(u) << '\n'; else cout << erase_(u) << '\n'; // if(id == 1) // { // int pos = -1; // for(int j = 1; j <= n, u; j ++) // { // if(dd[j]) continue; // dd[j] = 1, pos = a[j], u --; // } // cout << pos << '\n'; // } // else // { // int dem = 0; // while(dd[ pos[cha[u][0]] ]) u = cha[u][0], dem ++; // cout << dem << '\n', dd[pos[u]] = 0; // } } } int main() { iof(); int nTest = 1; // cin >> nTest; while(nTest --) { solve(); } ctime(); return 0; }

Compilation message (stderr)

ballmachine.cpp: In function 'void iof()':
ballmachine.cpp:17:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         freopen(Y8o".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp:18:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         freopen(Y8o".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...