oj.uz

Submission #242105

# Submission time Handle Problem Language Result Execution time Memory
242105 2020-06-26T19:38:46 Z LucaDantas Ball Machine (BOI13_ballmachine) C++17
24.7985 / 100
 245 ms 23024 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 = 1e5 + 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 6 ms 2688 KB Output isn't correct
2 Incorrect 135 ms 10872 KB Output isn't correct
3 Correct 79 ms 10488 KB Output is correct
4 Incorrect 6 ms 2688 KB Output isn't correct
5 Incorrect 6 ms 2816 KB Output isn't correct
6 Incorrect 6 ms 2816 KB Output isn't correct
7 Incorrect 7 ms 2816 KB Output isn't correct
8 Incorrect 7 ms 2816 KB Output isn't correct
9 Incorrect 12 ms 3200 KB Output isn't correct
10 Incorrect 28 ms 4736 KB Output isn't correct
11 Incorrect 133 ms 10744 KB Output isn't correct
12 Correct 77 ms 10488 KB Output is correct
13 Incorrect 113 ms 10360 KB Output isn't correct

Subtask #2
10.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 6520 KB Output is correct
2 Incorrect 193 ms 18420 KB Output isn't correct
3 Correct 96 ms 13936 KB Output is correct
4 Incorrect 91 ms 7928 KB Output isn't correct
5 Incorrect 109 ms 7800 KB Output isn't correct
6 Incorrect 100 ms 7548 KB Output isn't correct
7 Incorrect 85 ms 7032 KB Output isn't correct
8 Correct 49 ms 6648 KB Output is correct
9 Incorrect 176 ms 18544 KB Output isn't correct
10 Incorrect 193 ms 18420 KB Output isn't correct
11 Incorrect 162 ms 17780 KB Output isn't correct
12 Incorrect 183 ms 16360 KB Output isn't correct
13 Correct 119 ms 19824 KB Output is correct
14 Correct 96 ms 13936 KB Output is correct

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 85 ms 10996 KB Output isn't correct
2 Incorrect 208 ms 17140 KB Output isn't correct
3 Correct 151 ms 18796 KB Output is correct
4 Incorrect 131 ms 15596 KB Output isn't correct
5 Incorrect 123 ms 15220 KB Output isn't correct
6 Incorrect 138 ms 15348 KB Output isn't correct
7 Incorrect 129 ms 14068 KB Output isn't correct
8 Correct 154 ms 18800 KB Output is correct
9 Incorrect 195 ms 19024 KB Output isn't correct
10 Incorrect 205 ms 18668 KB Output isn't correct
11 Incorrect 222 ms 18804 KB Output isn't correct
12 Incorrect 199 ms 17172 KB Output isn't correct
13 Correct 245 ms 23024 KB Output is correct
14 Incorrect 140 ms 14832 KB Output isn't correct

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 210 ms 18796 KB Output isn't correct
2 Incorrect 205 ms 16876 KB Output isn't correct
3 Correct 130 ms 22004 KB Output is correct
4 Incorrect 230 ms 18800 KB Output isn't correct
5 Incorrect 200 ms 18420 KB Output isn't correct
6 Incorrect 165 ms 17776 KB Output isn't correct
7 Incorrect 213 ms 17008 KB Output isn't correct
8 Correct 132 ms 22004 KB Output is correct
9 Correct 95 ms 13936 KB Output is correct