oj.uz

답안 #648617

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
648617 2022-10-07T07:15:46 Z ghostwriter Ball Machine (BOI13_ballmachine) C++14
100 / 100
 153 ms 23484 KB 
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <debug.h>
#else
#define debug(...)
#endif
#define ft front
#define bk back
#define st first
#define nd second
#define ins insert
#define ers erase
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define mtp make_tuple
#define bg begin
#define ed end
#define all(x) (x).bg(), (x).ed()
#define sz(x) (int)(x).size()
typedef long long ll; typedef unsigned long long ull;
typedef double db; typedef long double ldb;
typedef pair<int, int> pi; typedef pair<ll, ll> pll;
typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll;
typedef string str;
template<typename T> T gcd(T a, T b) { return (b == 0? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
#define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
#define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
#define FSN(i, n) for (int (i) = (n) - 1; (i) >= 0; --(i))
#define EACH(i, x) for (auto &(i) : (x))
#define WHILE while
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
/*
----------------------------------------------------------------
    END OF TEMPLATE
----------------------------------------------------------------
    Tran The Bao - ghostwriter
    Training for VOI23 gold medal
----------------------------------------------------------------
    DIT ME CHUYEN BAO LOC
----------------------------------------------------------------
*/
const int N = 1e5 + 5;
int n, q, minn[N], h[N], s[N], tout[N], itout[N], p[N][17], timer = 0, root = 0, f[N], f1[N];
vi adj[N];
void dfs(int u) {
	minn[u] = u;
	EACH(v, adj[u]) {
		dfs(v);
		minn[u] = min(minn[u], minn[v]);
	}
}
bool cmp(int a, int b) { return minn[a] < minn[b]; }
void dfs1(int u) {
	FOR(j, 1, 16) ::p[u][j] = ::p[::p[u][j - 1]][j - 1];
	s[u] = 1;
	sort(all(adj[u]), cmp);
	EACH(v, adj[u]) {
		h[v] = h[u] + 1;
		p[v][0] = u;
		dfs1(v);
		s[u] += s[v];
	}
	tout[u] = ++timer;
}
int getn(int a, int h) {
	FOR(i, 0, 16)
		if (h & (1 << i))
			a = p[a][i];
	return a;
}
void upd(int pos, int v) { for (int i = pos; i <= n; i += (i & -i)) f[i] += v; }
int fempty() {
	int cur = 0, cnt = 0, ans = n + 1;
	FOS(i, 16, 0) {
		if (cur + (1 << i) > n) continue;
		if (cnt + f[cur + (1 << i)] < cur + (1 << i)) ans = min(ans, cur + (1 << i));
		else {
			cur |= 1 << i;
			cnt += f[cur];
		}
	}
	return ans;
}
void upd1(int pos, int v) { for (int i = pos; i <= n; i += (i & -i)) f1[i] += v; }
void upd1(int l, int r, int v) { upd1(l, v); upd1(r + 1, -v); }
int get1(int pos) { int rs = 0; for (int i = pos; i >= 1; i -= (i & -i)) rs += f1[i]; return rs; }
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    // freopen(file".inp", "r", stdin);
    // freopen(file".out", "w", stdout);
    cin >> n >> q;
    FOR(i, 1, n) {
    	int p;
    	cin >> p;
    	if (p) adj[p].pb(i);
    	else root = i;
    }
    dfs(root);
    dfs1(root);
    FOR(i, 1, n) itout[tout[i]] = i;
    WHILE(q--) {
    	int t;
    	cin >> t;
    	if (t == 1) {
    		int k, last = 0;
    		cin >> k;
    		FOR(i, 1, k) {
    			int pos = itout[fempty()];
    			upd(tout[pos], 1);
    			upd1(tout[pos] - s[pos] + 1, tout[pos], 1);
    			last = pos;
    		}
    		cout << last << '\n';
    		continue;
    	}
    	int x;
    	cin >> x;
    	int h = get1(tout[x]);
    	cout << h - 1 << '\n';
    	int tnode = getn(x, h - 1);
    	upd(tout[tnode], -1);
    	upd1(tout[tnode] - s[tnode] + 1, tout[tnode], -1);
    }
    return 0;
}
/*
8 2
0
1
2
2
3
3
4
6
1 8
2 5
----------------------------------------------------------------
From Benq:
    stuff you should look for
        * int overflow, array bounds
        * special cases (n=1?)
        * do smth instead of nothing and stay organized
        * WRITE STUFF DOWN
        * DON'T GET STUCK ON ONE APPROACH
----------------------------------------------------------------
*/

Compilation message

ballmachine.cpp: In function 'void dfs(int)':
ballmachine.cpp:36:31: warning: unnecessary parentheses in declaration of 'v' [-Wparentheses]
   36 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
ballmachine.cpp:56:2: note: in expansion of macro 'EACH'
   56 |  EACH(v, adj[u]) {
      |  ^~~~
ballmachine.cpp: In function 'void dfs1(int)':
ballmachine.cpp:32:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   32 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
ballmachine.cpp:63:2: note: in expansion of macro 'FOR'
   63 |  FOR(j, 1, 16) ::p[u][j] = ::p[::p[u][j - 1]][j - 1];
      |  ^~~
ballmachine.cpp:36:31: warning: unnecessary parentheses in declaration of 'v' [-Wparentheses]
   36 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
ballmachine.cpp:66:2: note: in expansion of macro 'EACH'
   66 |  EACH(v, adj[u]) {
      |  ^~~~
ballmachine.cpp: In function 'int getn(int, int)':
ballmachine.cpp:32:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   32 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
ballmachine.cpp:75:2: note: in expansion of macro 'FOR'
   75 |  FOR(i, 0, 16)
      |  ^~~
ballmachine.cpp: In function 'int fempty()':
ballmachine.cpp:33:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   33 | #define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
      |                               ^
ballmachine.cpp:83:2: note: in expansion of macro 'FOS'
   83 |  FOS(i, 16, 0) {
      |  ^~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:32:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   32 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
ballmachine.cpp:101:5: note: in expansion of macro 'FOR'
  101 |     FOR(i, 1, n) {
      |     ^~~
ballmachine.cpp:32:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   32 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
ballmachine.cpp:109:5: note: in expansion of macro 'FOR'
  109 |     FOR(i, 1, n) itout[tout[i]] = i;
      |     ^~~
ballmachine.cpp:32:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   32 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
ballmachine.cpp:116:7: note: in expansion of macro 'FOR'
  116 |       FOR(i, 1, k) {
      |       ^~~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 73 ms 10388 KB Output is correct
3 Correct 52 ms 10112 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 6 ms 3156 KB Output is correct
10 Correct 16 ms 4476 KB Output is correct
11 Correct 68 ms 10392 KB Output is correct
12 Correct 51 ms 10152 KB Output is correct
13 Correct 68 ms 10060 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 6564 KB Output is correct
2 Correct 124 ms 18416 KB Output is correct
3 Correct 67 ms 13076 KB Output is correct
4 Correct 43 ms 7840 KB Output is correct
5 Correct 44 ms 7804 KB Output is correct
6 Correct 43 ms 7580 KB Output is correct
7 Correct 42 ms 6740 KB Output is correct
8 Correct 27 ms 6576 KB Output is correct
9 Correct 102 ms 18800 KB Output is correct
10 Correct 112 ms 18372 KB Output is correct
11 Correct 100 ms 17992 KB Output is correct
12 Correct 114 ms 16056 KB Output is correct
13 Correct 96 ms 20344 KB Output is correct
14 Correct 69 ms 13028 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 10632 KB Output is correct
2 Correct 131 ms 16848 KB Output is correct
3 Correct 85 ms 19148 KB Output is correct
4 Correct 84 ms 15548 KB Output is correct
5 Correct 79 ms 15232 KB Output is correct
6 Correct 78 ms 15180 KB Output is correct
7 Correct 81 ms 13692 KB Output is correct
8 Correct 100 ms 19156 KB Output is correct
9 Correct 120 ms 18696 KB Output is correct
10 Correct 131 ms 18248 KB Output is correct
11 Correct 119 ms 18572 KB Output is correct
12 Correct 112 ms 16884 KB Output is correct
13 Correct 153 ms 23484 KB Output is correct
14 Correct 83 ms 14024 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 132 ms 19036 KB Output is correct
2 Correct 119 ms 16712 KB Output is correct
3 Correct 97 ms 22628 KB Output is correct
4 Correct 135 ms 18996 KB Output is correct
5 Correct 130 ms 18440 KB Output is correct
6 Correct 123 ms 18124 KB Output is correct
7 Correct 118 ms 16716 KB Output is correct
8 Correct 98 ms 22656 KB Output is correct
9 Correct 70 ms 13124 KB Output is correct