oj.uz

답안 #230476

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
230476 2020-05-10T08:00:24 Z alishahali1382 Ball Machine (BOI13_ballmachine) C++14
100 / 100
 238 ms 23804 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int MAXN=100010, LOG=18;

int n, m, k, u, v, x, y, t, a, b, ans;
int par[MAXN][LOG], mn[MAXN], h[MAXN];
int stt[MAXN], fnt[MAXN], ras[MAXN], timer;
int dead[MAXN], cnt[MAXN];
vector<int> G[MAXN];
set<pii> st;

void dfs1(int node){
	mn[node]=node;
	for (int v:G[node]){
		h[v]=h[node]+1;
		dfs1(v);
		mn[node]=min(mn[node], mn[v]);
		cnt[node]++;
	}
}

void dfs2(int node){
	ras[stt[node]=timer++]=node;
	sort(all(G[node]), [](int i, int j){
		return mn[i]<mn[j];
	});
	for (int v:G[node]) dfs2(v);
	fnt[node]=timer;
}

int AddBall(){
	int v=st.begin()->second;
	st.erase(st.begin());
	dead[v]=1;
	if (!--cnt[par[v][0]] && !dead[par[v][0]]) st.insert({stt[par[v][0]], par[v][0]});
	return v;
}

int RemBall(int v){
	for (int i=LOG-1; ~i; i--) if (dead[par[v][i]]) v=par[v][i];
	dead[v]=0;
	if (!cnt[v]) st.insert({stt[v], v});
	if (!cnt[par[v][0]]++) st.erase({stt[par[v][0]], par[v][0]});
	return v;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n>>m;
	for (int i=1; i<=n; i++){
		cin>>par[i][0];
		G[par[i][0]].pb(i);
	}
	for (int j=1; j<LOG; j++) for (int i=1; i<=n; i++) par[i][j]=par[par[i][j-1]][j-1];
	dfs1(0);
	dfs2(0);
	for (int v=1; v<=n; v++) if (!cnt[v] && !dead[v]) st.insert({stt[v], v});
	
	while (m--){
		cin>>t>>x;
		if (t==1){
			while (x--) ans=AddBall();
			cout<<ans<<'\n';
			continue ;
		}
		ans=RemBall(x);
		cout<<h[x]-h[ans]<<'\n';
	}
	
	return 0;
}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 2816 KB Output is correct
2 Correct 144 ms 13024 KB Output is correct
3 Correct 73 ms 12792 KB Output is correct
4 Correct 6 ms 2688 KB Output is correct
5 Correct 6 ms 2816 KB Output is correct
6 Correct 6 ms 2816 KB Output is correct
7 Correct 7 ms 2816 KB Output is correct
8 Correct 7 ms 2944 KB Output is correct
9 Correct 14 ms 3328 KB Output is correct
10 Correct 29 ms 5248 KB Output is correct
11 Correct 155 ms 13052 KB Output is correct
12 Correct 93 ms 12792 KB Output is correct
13 Correct 124 ms 13048 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 6904 KB Output is correct
2 Correct 213 ms 20856 KB Output is correct
3 Correct 99 ms 17524 KB Output is correct
4 Correct 74 ms 8568 KB Output is correct
5 Correct 82 ms 8568 KB Output is correct
6 Correct 78 ms 8696 KB Output is correct
7 Correct 86 ms 7800 KB Output is correct
8 Correct 45 ms 6904 KB Output is correct
9 Correct 155 ms 20728 KB Output is correct
10 Correct 199 ms 20856 KB Output is correct
11 Correct 157 ms 20908 KB Output is correct
12 Correct 170 ms 18936 KB Output is correct
13 Correct 102 ms 20856 KB Output is correct
14 Correct 92 ms 17524 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 79 ms 11768 KB Output is correct
2 Correct 215 ms 19424 KB Output is correct
3 Correct 125 ms 19320 KB Output is correct
4 Correct 140 ms 17072 KB Output is correct
5 Correct 138 ms 17144 KB Output is correct
6 Correct 148 ms 17144 KB Output is correct
7 Correct 147 ms 15864 KB Output is correct
8 Correct 127 ms 19448 KB Output is correct
9 Correct 216 ms 20808 KB Output is correct
10 Correct 232 ms 21116 KB Output is correct
11 Correct 234 ms 21088 KB Output is correct
12 Correct 231 ms 19572 KB Output is correct
13 Correct 195 ms 23804 KB Output is correct
14 Correct 208 ms 18368 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 233 ms 20932 KB Output is correct
2 Correct 223 ms 19428 KB Output is correct
3 Correct 136 ms 23084 KB Output is correct
4 Correct 238 ms 20984 KB Output is correct
5 Correct 215 ms 20988 KB Output is correct
6 Correct 185 ms 20960 KB Output is correct
7 Correct 229 ms 19552 KB Output is correct
8 Correct 112 ms 23008 KB Output is correct
9 Correct 107 ms 17632 KB Output is correct