oj.uz

Submission #242101

# Submission time Handle Problem Language Result Execution time Memory
242101 2020-06-26T19:21:17 Z LucaDantas Ball Machine (BOI13_ballmachine) C++17
27.5397 / 100
 242 ms 28532 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 16052 KB Output isn't correct
3 Incorrect 84 ms 15992 KB Output isn't correct
4 Incorrect 9 ms 7424 KB Output isn't correct
5 Incorrect 9 ms 7424 KB Output isn't correct
6 Incorrect 10 ms 7552 KB Output isn't correct
7 Incorrect 10 ms 7552 KB Output isn't correct
8 Incorrect 10 ms 7552 KB Output isn't correct
9 Incorrect 17 ms 8064 KB Output isn't correct
10 Incorrect 33 ms 9728 KB Output isn't correct
11 Incorrect 139 ms 16376 KB Output isn't correct
12 Incorrect 88 ms 15988 KB Output isn't correct
13 Incorrect 135 ms 15968 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 11640 KB Output is correct
2 Incorrect 196 ms 24180 KB Output isn't correct
3 Incorrect 104 ms 19952 KB Output isn't correct
4 Incorrect 98 ms 12920 KB Output isn't correct
5 Incorrect 95 ms 13048 KB Output isn't correct
6 Incorrect 91 ms 12920 KB Output isn't correct
7 Incorrect 100 ms 12304 KB Output isn't correct
8 Correct 60 ms 11640 KB Output is correct
9 Incorrect 183 ms 24816 KB Output isn't correct
10 Incorrect 195 ms 24176 KB Output isn't correct
11 Incorrect 176 ms 24036 KB Output isn't correct
12 Incorrect 193 ms 22512 KB Output isn't correct
13 Correct 137 ms 25328 KB Output is correct
14 Incorrect 102 ms 20080 KB Output isn't correct

Subtask #3
20.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 95 ms 16096 KB Output isn't correct
2 Correct 231 ms 22620 KB Output is correct
3 Correct 151 ms 24044 KB Output is correct
4 Incorrect 135 ms 20976 KB Output isn't correct
5 Incorrect 133 ms 20724 KB Output isn't correct
6 Incorrect 136 ms 20848 KB Output isn't correct
7 Incorrect 135 ms 19572 KB Output isn't correct
8 Correct 147 ms 24176 KB Output is correct
9 Incorrect 205 ms 24560 KB Output isn't correct
10 Correct 219 ms 24176 KB Output is correct
11 Correct 229 ms 24180 KB Output is correct
12 Correct 224 ms 22640 KB Output is correct
13 Correct 242 ms 28532 KB Output is correct
14 Incorrect 156 ms 20336 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 224 ms 24460 KB Output isn't correct
2 Incorrect 199 ms 22644 KB Output isn't correct
3 Correct 152 ms 27508 KB Output is correct
4 Incorrect 220 ms 24432 KB Output isn't correct
5 Incorrect 194 ms 24180 KB Output isn't correct
6 Incorrect 182 ms 23952 KB Output isn't correct
7 Incorrect 218 ms 22640 KB Output isn't correct
8 Correct 149 ms 27508 KB Output is correct
9 Incorrect 117 ms 20080 KB Output isn't correct