oj.uz

Submission #242108

# Submission time Handle Problem Language Result Execution time Memory
242108 2020-06-26T19:40:57 Z LucaDantas Ball Machine (BOI13_ballmachine) C++17
24.7985 / 100
 232 ms 25460 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 = 2e5 + 10;
constexpr int LOGN = 20;
constexpr int mod = 1000000007;

int n, root;

int pai[MAXN][LOGN], 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
3.84615384615 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 5120 KB Output isn't correct
2 Incorrect 130 ms 13048 KB Output isn't correct
3 Correct 88 ms 12792 KB Output is correct
4 Incorrect 8 ms 5120 KB Output isn't correct
5 Incorrect 7 ms 5120 KB Output isn't correct
6 Incorrect 8 ms 5376 KB Output isn't correct
7 Incorrect 8 ms 5248 KB Output isn't correct
8 Incorrect 12 ms 5248 KB Output isn't correct
9 Incorrect 14 ms 5632 KB Output isn't correct
10 Incorrect 30 ms 7168 KB Output isn't correct
11 Incorrect 128 ms 13048 KB Output isn't correct
12 Correct 85 ms 12792 KB Output is correct
13 Incorrect 121 ms 12700 KB Output isn't correct

Subtask #2
10.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 8952 KB Output is correct
2 Incorrect 201 ms 20684 KB Output isn't correct
3 Correct 101 ms 16240 KB Output is correct
4 Incorrect 96 ms 10284 KB Output isn't correct
5 Incorrect 90 ms 10112 KB Output isn't correct
6 Incorrect 87 ms 9976 KB Output isn't correct
7 Incorrect 98 ms 9336 KB Output isn't correct
8 Correct 53 ms 8956 KB Output is correct
9 Incorrect 181 ms 20976 KB Output isn't correct
10 Incorrect 222 ms 20724 KB Output isn't correct
11 Incorrect 187 ms 20212 KB Output isn't correct
12 Incorrect 215 ms 18684 KB Output isn't correct
13 Correct 120 ms 22256 KB Output is correct
14 Correct 102 ms 16240 KB Output is correct

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 95 ms 13428 KB Output isn't correct
2 Incorrect 208 ms 19448 KB Output isn't correct
3 Correct 142 ms 21104 KB Output is correct
4 Incorrect 126 ms 17904 KB Output isn't correct
5 Incorrect 159 ms 17760 KB Output isn't correct
6 Incorrect 146 ms 17652 KB Output isn't correct
7 Incorrect 120 ms 16372 KB Output isn't correct
8 Correct 145 ms 21252 KB Output is correct
9 Incorrect 198 ms 21360 KB Output isn't correct
10 Incorrect 212 ms 20976 KB Output isn't correct
11 Incorrect 204 ms 20980 KB Output isn't correct
12 Incorrect 196 ms 19572 KB Output isn't correct
13 Correct 232 ms 25460 KB Output is correct
14 Incorrect 144 ms 17264 KB Output isn't correct

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 208 ms 21232 KB Output isn't correct
2 Incorrect 191 ms 19180 KB Output isn't correct
3 Correct 145 ms 24388 KB Output is correct
4 Incorrect 209 ms 21360 KB Output isn't correct
5 Incorrect 202 ms 20724 KB Output isn't correct
6 Incorrect 177 ms 20076 KB Output isn't correct
7 Incorrect 221 ms 19312 KB Output isn't correct
8 Correct 150 ms 24468 KB Output is correct
9 Correct 102 ms 16368 KB Output is correct