oj.uz

Submission #242104

# Submission time Handle Problem Language Result Execution time Memory
242104 2020-06-26T19:36:17 Z LucaDantas Ball Machine (BOI13_ballmachine) C++17
100 / 100
 231 ms 28528 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() {
	assert(!q.empty());
	int now = q.top(); // db(now);
	q.pop();
	act[now] = 1;
	upd(in[now], 1);
	upd(out[now], -1);
	return now;
}

void remove(int k) {
	// db(act[k]);
	assert(act[k]);
	dec(i,LOGN,0) {
		if(pai[k][i] == 0) continue;
		if(act[pai[k][i]]) k = pai[k][i];
	}
	// assert(act[k]);
	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);

	// int oi, cnta = 0;
	// while(1) { cin >> oi; db(oi); db(cnta++); }

	rep(i,1,n+1) q.push(i);
	// rep(i,0,n) { db(q.top()); q.pop(); }

	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 
		}
	}
	// rep(i,1,n+1) { db(i), db(act[i]); }
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:115: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:117: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:135: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 133 ms 15992 KB Output is correct
3 Correct 83 ms 15868 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct
5 Correct 9 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 31 ms 9600 KB Output is correct
11 Correct 130 ms 15916 KB Output is correct
12 Correct 87 ms 15732 KB Output is correct
13 Correct 121 ms 15608 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 11516 KB Output is correct
2 Correct 193 ms 23572 KB Output is correct
3 Correct 111 ms 19440 KB Output is correct
4 Correct 90 ms 12664 KB Output is correct
5 Correct 96 ms 12628 KB Output is correct
6 Correct 92 ms 12408 KB Output is correct
7 Correct 87 ms 11640 KB Output is correct
8 Correct 53 ms 11384 KB Output is correct
9 Correct 223 ms 23920 KB Output is correct
10 Correct 215 ms 23540 KB Output is correct
11 Correct 175 ms 23156 KB Output is correct
12 Correct 181 ms 21616 KB Output is correct
13 Correct 126 ms 25212 KB Output is correct
14 Correct 104 ms 19520 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 15988 KB Output is correct
2 Correct 202 ms 22516 KB Output is correct
3 Correct 156 ms 24176 KB Output is correct
4 Correct 129 ms 20848 KB Output is correct
5 Correct 131 ms 20468 KB Output is correct
6 Correct 142 ms 20592 KB Output is correct
7 Correct 130 ms 19320 KB Output is correct
8 Correct 143 ms 24176 KB Output is correct
9 Correct 192 ms 24560 KB Output is correct
10 Correct 211 ms 24176 KB Output is correct
11 Correct 214 ms 24052 KB Output is correct
12 Correct 220 ms 22644 KB Output is correct
13 Correct 227 ms 28528 KB Output is correct
14 Correct 144 ms 20464 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 24432 KB Output is correct
2 Correct 231 ms 22384 KB Output is correct
3 Correct 140 ms 27508 KB Output is correct
4 Correct 209 ms 24432 KB Output is correct
5 Correct 215 ms 23872 KB Output is correct
6 Correct 172 ms 23280 KB Output is correct
7 Correct 201 ms 22348 KB Output is correct
8 Correct 147 ms 27612 KB Output is correct
9 Correct 110 ms 19440 KB Output is correct