oj.uz

Submission #242107

# Submission time Handle Problem Language Result Execution time Memory
242107 2020-06-26T19:40:03 Z LucaDantas Ball Machine (BOI13_ballmachine) C++17
24.7985 / 100
 240 ms 25456 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 8 ms 5120 KB Output isn't correct
2 Incorrect 142 ms 13048 KB Output isn't correct
3 Correct 95 ms 12788 KB Output is correct
4 Incorrect 7 ms 5120 KB Output isn't correct
5 Incorrect 8 ms 5120 KB Output isn't correct
6 Incorrect 8 ms 5224 KB Output isn't correct
7 Incorrect 8 ms 5248 KB Output isn't correct
8 Incorrect 8 ms 5248 KB Output isn't correct
9 Incorrect 16 ms 5632 KB Output isn't correct
10 Incorrect 31 ms 7168 KB Output isn't correct
11 Incorrect 134 ms 13100 KB Output isn't correct
12 Correct 83 ms 12792 KB Output is correct
13 Incorrect 115 ms 12664 KB Output isn't correct

Subtask #2
10.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 9084 KB Output is correct
2 Incorrect 208 ms 20720 KB Output isn't correct
3 Correct 99 ms 16236 KB Output is correct
4 Incorrect 102 ms 10232 KB Output isn't correct
5 Incorrect 91 ms 10116 KB Output isn't correct
6 Incorrect 84 ms 9848 KB Output isn't correct
7 Incorrect 90 ms 9464 KB Output isn't correct
8 Correct 52 ms 8952 KB Output is correct
9 Incorrect 197 ms 20976 KB Output isn't correct
10 Incorrect 198 ms 20724 KB Output isn't correct
11 Incorrect 165 ms 20212 KB Output isn't correct
12 Incorrect 198 ms 18800 KB Output isn't correct
13 Correct 150 ms 22248 KB Output is correct
14 Correct 105 ms 16344 KB Output is correct

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 87 ms 13300 KB Output isn't correct
2 Incorrect 195 ms 19368 KB Output isn't correct
3 Correct 153 ms 21296 KB Output is correct
4 Incorrect 128 ms 17904 KB Output isn't correct
5 Incorrect 144 ms 17652 KB Output isn't correct
6 Incorrect 130 ms 17648 KB Output isn't correct
7 Incorrect 130 ms 16344 KB Output isn't correct
8 Correct 143 ms 21144 KB Output is correct
9 Incorrect 197 ms 21356 KB Output isn't correct
10 Incorrect 204 ms 21100 KB Output isn't correct
11 Incorrect 208 ms 20980 KB Output isn't correct
12 Incorrect 196 ms 19444 KB Output isn't correct
13 Correct 240 ms 25456 KB Output is correct
14 Incorrect 150 ms 17136 KB Output isn't correct

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 211 ms 21104 KB Output isn't correct
2 Incorrect 212 ms 19312 KB Output isn't correct
3 Correct 130 ms 24440 KB Output is correct
4 Incorrect 216 ms 21104 KB Output isn't correct
5 Incorrect 220 ms 20728 KB Output isn't correct
6 Incorrect 173 ms 20080 KB Output isn't correct
7 Incorrect 215 ms 19188 KB Output isn't correct
8 Correct 146 ms 24560 KB Output is correct
9 Correct 98 ms 16248 KB Output is correct