oj.uz

Submission #535498

# Submission time Handle Problem Language Result Execution time Memory
535498 2022-03-10T11:42:28 Z faik Ball Machine (BOI13_ballmachine) C++14
100 / 100
 242 ms 39228 KB 
#include <bits/stdc++.h>

using namespace std;

#define MOD 998244353
#define INF 1000000001
#define LNF 1000000000000000001

#define int ll

typedef long long ll;
typedef pair<int,int> pii;

int dfsmin(int x,int last,vector<vector<int> > &edges,vector<int> &mn, vector<int> &height){
	if(last == x)
		height[x] = 0;
	else
		height[x] = height[last]+1;

	int ret = x;
	for(int i : edges[x]){
		if(i != last){
			ret = min(ret,dfsmin(i,x,edges,mn,height));
		}
	}
	sort(edges[x].begin(), edges[x].end(),[&mn](int a,int b){return mn[a] < mn[b];});
	mn[x] = ret;
	return ret;
}

void dfssec(int x,int last,vector<vector<int> > &edges, vector<int> &sec){
	static int counter = 0;
	for(int i : edges[x]){
		if(i != last){
			dfssec(i,x,edges,sec);
		}
	}
	sec[x] = counter++;
}
int l;

int lg(int x){
	int cnt = 0;
	while(x){x>>=1;cnt++;}
	return cnt;
}

void solve(){
//#define TEST
	int n,q;cin >> n >> q;
	vector<vector<int> > edges(n);
	vector<int> parent(n);
	int root;
	for(int i = 0;i < n;i++){
		int p;cin >> p;p--;
		if(p != -1){
			edges[i].push_back(p);
			edges[p].push_back(i);
			parent[i] = p;
		} else {
			parent[i] = i;
			root = i;
		}
	}

	vector<int> height(n);
	vector<int> mn(n);
	dfsmin(root,root,edges,mn,height);
	
	vector<int> sec(n);
	dfssec(root,root,edges,sec);
	priority_queue<pii,vector<pii>,greater<pii>> pq;
	for(int i = 0;i < n;i++){
		pq.push({sec[i],i});
	}

	l = lg(n);
	vector<vector<int> > up(n);
	up.assign(n,vector<int>(l+1,0));
	for(int i = 0;i < n;i++)
		up[i][0] = parent[i];

	for(int i = 1;i <= l;i++){
		for(int j = 0;j < n;j++){
			up[j][i] = up[up[j][i-1]][i-1];
		}
	}
	vector<int> filled(n);
	for(int t = 0;t < q;t++){
		int i,x;cin >> i >> x;
		if(i == 1){
			int last;
			for(int j = 0;j < x;j++){
				last = pq.top().second;
				pq.pop();
				filled[last] = true;
			}
			cout << last+1 << '\n';
		} else if(i == 2){
			x--;
			int next = x;
			for(int j = l;j >= 0;j--){
				while(filled[up[next][j]] && next != root){
					next = up[next][j];
				}
			}
			filled[next] = false;
			pq.push({sec[next],next});
			cout << height[x]-height[next] << '\n';
		}
	}
}

signed main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
#ifdef DEBUG
	freopen("i.txt","r",stdin);
	freopen("o.txt","w",stdout);
#endif
	int t = 1;
#ifdef TEST
	cin >> t;
#endif
	while(t--){
		solve();
	}

	return 0;
}

Compilation message

ballmachine.cpp: In function 'void solve()':
ballmachine.cpp:98:17: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
   98 |    cout << last+1 << '\n';
      |                 ^
ballmachine.cpp:103:31: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  103 |     while(filled[up[next][j]] && next != root){

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 116 ms 19252 KB Output is correct
3 Correct 73 ms 19460 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 5 ms 1364 KB Output is correct
10 Correct 18 ms 4808 KB Output is correct
11 Correct 118 ms 19264 KB Output is correct
12 Correct 73 ms 19356 KB Output is correct
13 Correct 95 ms 19204 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 7336 KB Output is correct
2 Correct 191 ms 34620 KB Output is correct
3 Correct 103 ms 29852 KB Output is correct
4 Correct 54 ms 10132 KB Output is correct
5 Correct 48 ms 10156 KB Output is correct
6 Correct 44 ms 10204 KB Output is correct
7 Correct 52 ms 8728 KB Output is correct
8 Correct 30 ms 7244 KB Output is correct
9 Correct 191 ms 34472 KB Output is correct
10 Correct 182 ms 34612 KB Output is correct
11 Correct 157 ms 34648 KB Output is correct
12 Correct 184 ms 31636 KB Output is correct
13 Correct 117 ms 34464 KB Output is correct
14 Correct 92 ms 29908 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 16616 KB Output is correct
2 Correct 242 ms 32448 KB Output is correct
3 Correct 138 ms 31236 KB Output is correct
4 Correct 133 ms 27708 KB Output is correct
5 Correct 167 ms 27888 KB Output is correct
6 Correct 128 ms 28068 KB Output is correct
7 Correct 116 ms 25892 KB Output is correct
8 Correct 142 ms 31292 KB Output is correct
9 Correct 217 ms 34632 KB Output is correct
10 Correct 222 ms 34888 KB Output is correct
11 Correct 214 ms 34880 KB Output is correct
12 Correct 200 ms 32452 KB Output is correct
13 Correct 241 ms 39228 KB Output is correct
14 Correct 152 ms 29988 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 34724 KB Output is correct
2 Correct 194 ms 32440 KB Output is correct
3 Correct 166 ms 39052 KB Output is correct
4 Correct 197 ms 34756 KB Output is correct
5 Correct 199 ms 34808 KB Output is correct
6 Correct 201 ms 34776 KB Output is correct
7 Correct 186 ms 32464 KB Output is correct
8 Correct 131 ms 39060 KB Output is correct
9 Correct 90 ms 29968 KB Output is correct