oj.uz

Submission #242106

# Submission time Handle Problem Language Result Execution time Memory
242106 2020-06-26T19:39:26 Z LucaDantas Ball Machine (BOI13_ballmachine) C++17
100 / 100
 239 ms 28524 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

#ifdef MY_DEBUG_FLAG
template<typename T> void debug(T a) { cerr << a << ' '; }
template<typename T, typename U> void debug(pair<T, U> a) { cerr << a.first << ' ' << a.second << ' '; }
template<typename T> void debug(vector<T> a) { for(auto it : a) debug(it);}
template<typename T> void debug(set<T> a) { for(auto it : a) debug(it);}
#define db(a) cerr << "DEBUG ( " << #a << " == "; debug(a); cerr << ")\n"
#else
#define db(...)
#endif

#define pb push_back
#define ff first
#define ss second
#define fast ios_base::sync_with_stdio(false), cout.tie(nullptr), cin.tie(nullptr)
#define sz(a) ((int)(a).size())
#define rep(i,a,b) for(int i=(a); i<(b); i++)
#define dec(i,n,a) for(int i=(n); i>=(a); i--)
#define clr(a,v) memset(a, v, sizeof(a))
#define all(a) (a).begin(),(a).end()

constexpr int inf = 0x3f3f3f3f;
constexpr int MAXN = 3e5 + 10;
constexpr int LOGN = 20;
constexpr int mod = 1000000007;

int n, root;

int pai[MAXN][LOGN+2], menor[MAXN], in[MAXN], out[MAXN], aux = 0;

bool act[MAXN];

vi g[MAXN]; // contains only the children of a node

void calc_menor(int u) {
	menor[u] = u;
	for(auto v : g[u]) {
		calc_menor(v);
		menor[u] = min(menor[u], menor[v]);
	}
}

void dfs(int u) {
	in[u] = aux++; db(u); db(in[u]);
	sort(all(g[u]), [](const int& a, const int& b) {
		return menor[a] < menor[b];
	}); db(g[u]);
	for(auto v : g[u]) {
		dfs(v);
	}
	out[u] = aux++;
}

struct comp {
	bool operator()(const int& a, const int& b) {
		return out[a] > out[b];
	}
};

priority_queue<int, vector<int>, comp> q;

void binary_parents() {
	for(int j = 1; j < LOGN; j++) {
		for(int i = 1; i <= n; i++) {
			if(pai[i][j-1] == 0) continue;
			pai[i][j] = pai[pai[i][j-1]][j-1];
		}
	}
}

int bit[2*MAXN];

void upd(int x, int v) {
	for(x++; x < 2*MAXN; x += x&-x)
		bit[x] += v;
}

int query(int x) {
	int ans = 0;
	for(x++; x > 0; x -= x&-x)
		ans += bit[x];
	return ans;
}

int add() {
	int now = q.top();
	q.pop();
	act[now] = 1;
	upd(in[now], 1);
	upd(out[now], -1);
	return now;
}

void remove(int k) {
	dec(i,LOGN,0) {
		if(pai[k][i] == 0) continue;
		if(act[pai[k][i]]) k = pai[k][i];
	}
	act[k] = 0;
	q.push(k);
	upd(in[k], -1); upd(out[k], 1);
}

int main() {
	int Q;
	scanf("%d %d", &n, &Q);
	rep(i,1,n+1) {
		int p; scanf("%d", &p);
		pai[i][0] = p;
		if(p == 0) root = i;
		else g[p].pb(i);
	}

	binary_parents();
	calc_menor(root);
	dfs(root);

	rep(i,1,n+1) q.push(i);

	while(Q--) {
		int type, k;
		scanf("%d %d", &type, &k);
		if(type == 1) {
			rep(i,0,k) {
				if(i == k-1) printf("%d\n", add());
				else add(); // returns the position that was added
			}
		}
		else {
			printf("%d\n", query(in[k])-1); // how many active parents he has
			remove(k); // removes the last parent of this guy 
		}
	}
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:111:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~
ballmachine.cpp:113:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int p; scanf("%d", &p);
          ~~~~~^~~~~~~~~~
ballmachine.cpp:127:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &type, &k);
   ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7552 KB Output is correct
2 Correct 137 ms 15868 KB Output is correct
3 Correct 85 ms 15736 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct
5 Correct 10 ms 7424 KB Output is correct
6 Correct 10 ms 7552 KB Output is correct
7 Correct 10 ms 7552 KB Output is correct
8 Correct 10 ms 7552 KB Output is correct
9 Correct 15 ms 7936 KB Output is correct
10 Correct 34 ms 9600 KB Output is correct
11 Correct 132 ms 15888 KB Output is correct
12 Correct 90 ms 15736 KB Output is correct
13 Correct 119 ms 15608 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 11384 KB Output is correct
2 Correct 190 ms 23796 KB Output is correct
3 Correct 107 ms 19440 KB Output is correct
4 Correct 91 ms 12816 KB Output is correct
5 Correct 88 ms 12536 KB Output is correct
6 Correct 83 ms 12288 KB Output is correct
7 Correct 84 ms 11640 KB Output is correct
8 Correct 54 ms 11384 KB Output is correct
9 Correct 177 ms 23920 KB Output is correct
10 Correct 199 ms 23568 KB Output is correct
11 Correct 172 ms 23284 KB Output is correct
12 Correct 182 ms 21616 KB Output is correct
13 Correct 128 ms 25312 KB Output is correct
14 Correct 102 ms 19440 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 15988 KB Output is correct
2 Correct 195 ms 22500 KB Output is correct
3 Correct 152 ms 24176 KB Output is correct
4 Correct 137 ms 20976 KB Output is correct
5 Correct 128 ms 20468 KB Output is correct
6 Correct 128 ms 20596 KB Output is correct
7 Correct 129 ms 19316 KB Output is correct
8 Correct 158 ms 24048 KB Output is correct
9 Correct 197 ms 24428 KB Output is correct
10 Correct 226 ms 24176 KB Output is correct
11 Correct 211 ms 24052 KB Output is correct
12 Correct 202 ms 22516 KB Output is correct
13 Correct 239 ms 28524 KB Output is correct
14 Correct 146 ms 20336 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 24300 KB Output is correct
2 Correct 214 ms 22256 KB Output is correct
3 Correct 139 ms 27636 KB Output is correct
4 Correct 216 ms 24304 KB Output is correct
5 Correct 199 ms 23664 KB Output is correct
6 Correct 167 ms 23280 KB Output is correct
7 Correct 196 ms 22252 KB Output is correct
8 Correct 138 ms 27508 KB Output is correct
9 Correct 104 ms 19440 KB Output is correct