Submission #30863

#	Time	Username	Problem	Language	Result	Execution time	Memory
30863		Navick	Ball Machine (BOI13_ballmachine)	C++14	39.45 / 100	579 ms	28148 KiB

ballmachine

#include <bits/stdc++.h>
#define F first
#define S second
#define pii pair<int, int>
#define pb push_back
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
const int N = 1e5 + 10, LOG = 18;
 
bool full[N];
vector<int> adj[N];
int n, root, g[N], mn[N], par[N][LOG], ord[N], turn = 0;
 
set<pii> st;
 
bool cmp(int u, int v){
	return mn[u] < mn[v];
}
 
bool pmc(int u, int v){
	return ord[u] < ord[v];
}
 
void p_dfs(int v, int p = 0){
	par[v][0] = p;
	for(int i=1; i<LOG; i++)
		par[v][i] = par[par[v][i - 1]][i - 1];
	
	mn[v] = v;
	for(auto u : adj[v]){
		p_dfs(u, v);
		mn[v] = min(mn[v], mn[u]);
	}
 
	sort(adj[v].begin(), adj[v].end(), cmp);
	
}
 
void dfs(int v){
	for(auto u : adj[v])
		dfs(u);
 
	ord[v] = turn++;
}
 
int add(){
	int v = (*st.begin()).S;
	st.erase(st.begin());
	full[v] = true;
	return v;
}
 
int erase(int v){
	int ans = 0;
	for(int i=LOG-1; i>=0; i--){
		if(full[par[v][i]]){
			ans += (1 << i);
			v = par[v][i];
		}
	}
	full[v] = false;
	st.insert({ord[v], v});
	return ans;
}
 
int main(){
	//ios_base::sync_with_stdio(0); cin.tie(0);
	int q; scanf("%d %d", &n, &q);
	for(int i=1; i<=n; i++){
		int p; scanf("%d", &p);
		if(p == 0)root = i;
		else adj[p].pb(i);
	}
 
	p_dfs(root);
	dfs(root);
 
	for(int i=0; i<n; i++)
		g[i] = i + 1;
 
	sort(g, g + n, pmc);
 
	for(int i=1; i<=n; i++)
		st.insert({ord[i], i});
 
	while(q--){
		int tp; cin >> tp;
		if(tp == 1){
			int k, pos = -1; scanf("%d", &k);
			while(k--)
				pos = add();
          printf("%d\n", pos);
		}else{
			int v; scanf("%d", &v);
			printf("%d\n", erase(v));
		}
	}
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:72:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int q; scanf("%d %d", &n, &q);
                               ^
ballmachine.cpp:74:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int p; scanf("%d", &p);
                         ^
ballmachine.cpp:93:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int k, pos = -1; scanf("%d", &k);
                                    ^
ballmachine.cpp:98:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int v; scanf("%d", &v);
                          ^

• Subtask 1: 17.307692307692307 / 25
• Subtask 2: 10.714285714285714 / 30
• Subtask 3: 11.428571428571429 / 40
• Subtask 4: 0 / 5