oj.uz

Submission #242099

# Submission time Handle Problem Language Result Execution time Memory
242099 2020-06-26T19:19:25 Z LucaDantas Ball Machine (BOI13_ballmachine) C++17
27.5397 / 100
 250 ms 28408 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

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

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

struct comp {
	bool operator()(const int& a, const int& b) {
		return in[a] < in[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]);
	dec(i,LOGN,0) {
		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);

	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:113: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:115: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:132: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
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 7424 KB Output isn't correct
2 Incorrect 155 ms 16796 KB Output isn't correct
3 Incorrect 89 ms 16504 KB Output isn't correct
4 Incorrect 9 ms 7424 KB Output isn't correct
5 Incorrect 10 ms 7424 KB Output isn't correct
6 Incorrect 11 ms 7552 KB Output isn't correct
7 Incorrect 11 ms 7552 KB Output isn't correct
8 Incorrect 10 ms 7552 KB Output isn't correct
9 Incorrect 16 ms 7936 KB Output isn't correct
10 Incorrect 33 ms 9728 KB Output isn't correct
11 Incorrect 142 ms 16760 KB Output isn't correct
12 Incorrect 84 ms 16504 KB Output isn't correct
13 Incorrect 128 ms 16504 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 11512 KB Output is correct
2 Incorrect 200 ms 24828 KB Output isn't correct
3 Incorrect 105 ms 20208 KB Output isn't correct
4 Incorrect 94 ms 13432 KB Output isn't correct
5 Incorrect 94 ms 13432 KB Output isn't correct
6 Incorrect 93 ms 13432 KB Output isn't correct
7 Incorrect 92 ms 12664 KB Output isn't correct
8 Correct 56 ms 11512 KB Output is correct
9 Incorrect 200 ms 25456 KB Output isn't correct
10 Incorrect 250 ms 24820 KB Output isn't correct
11 Incorrect 180 ms 24692 KB Output isn't correct
12 Incorrect 189 ms 23024 KB Output isn't correct
13 Correct 124 ms 25068 KB Output is correct
14 Incorrect 104 ms 20208 KB Output isn't correct

Subtask #3
20.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 93 ms 16484 KB Output isn't correct
2 Correct 202 ms 22772 KB Output is correct
3 Correct 151 ms 23996 KB Output is correct
4 Incorrect 156 ms 21360 KB Output isn't correct
5 Incorrect 137 ms 21160 KB Output isn't correct
6 Incorrect 133 ms 21088 KB Output isn't correct
7 Incorrect 148 ms 19956 KB Output isn't correct
8 Correct 145 ms 24044 KB Output is correct
9 Incorrect 216 ms 25196 KB Output isn't correct
10 Correct 210 ms 24432 KB Output is correct
11 Correct 221 ms 24312 KB Output is correct
12 Correct 205 ms 22772 KB Output is correct
13 Correct 244 ms 28408 KB Output is correct
14 Incorrect 159 ms 20980 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 213 ms 25072 KB Output isn't correct
2 Incorrect 207 ms 23304 KB Output isn't correct
3 Correct 137 ms 27380 KB Output is correct
4 Incorrect 228 ms 25200 KB Output isn't correct
5 Incorrect 207 ms 24888 KB Output isn't correct
6 Incorrect 188 ms 24688 KB Output isn't correct
7 Incorrect 197 ms 23408 KB Output isn't correct
8 Correct 146 ms 27376 KB Output is correct
9 Incorrect 103 ms 20336 KB Output isn't correct