oj.uz

답안 #242093

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
242093 2020-06-26T19:03:41 Z LucaDantas Ball Machine (BOI13_ballmachine) C++17
27.5397 / 100
 254 ms 48368 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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 19 ms 14976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 59 ms 30712 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 57 ms 30200 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 18 ms 14848 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 18 ms 14976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 19 ms 15104 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 19 ms 15104 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 19 ms 15232 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 20 ms 15872 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 28 ms 18936 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 65 ms 31016 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 52 ms 30200 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 58 ms 30328 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
6.42857142857 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 11384 KB Output is correct
2 Runtime error 106 ms 46068 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 87 ms 37872 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 42 ms 24824 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 37 ms 24312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 38 ms 24440 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 38 ms 22784 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Correct 56 ms 11384 KB Output is correct
9 Runtime error 117 ms 46320 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 114 ms 46068 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 119 ms 45684 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 106 ms 41968 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Correct 158 ms 24972 KB Output is correct
14 Runtime error 77 ms 38052 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
20.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 88 ms 31860 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Correct 230 ms 22352 KB Output is correct
3 Correct 163 ms 23784 KB Output is correct
4 Runtime error 109 ms 41048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 99 ms 40564 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 98 ms 40540 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 109 ms 38000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Correct 155 ms 23768 KB Output is correct
9 Runtime error 210 ms 48368 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Correct 231 ms 23920 KB Output is correct
11 Correct 224 ms 23900 KB Output is correct
12 Correct 229 ms 22364 KB Output is correct
13 Correct 254 ms 28244 KB Output is correct
14 Runtime error 112 ms 39920 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #4
1.11111111111 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 124 ms 46356 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 147 ms 43640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Correct 173 ms 27176 KB Output is correct
4 Runtime error 131 ms 46396 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 131 ms 46368 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 118 ms 45528 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 131 ms 43632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Correct 203 ms 27228 KB Output is correct
9 Runtime error 71 ms 38000 KB Execution killed with signal 11 (could be triggered by violating memory limits)