oj.uz

Submission #110431

# Submission time Handle Problem Language Result Execution time Memory
110431 2019-05-10T20:30:28 Z wilwxk Ball Machine (BOI13_ballmachine) C++11
20.9524 / 100
 1000 ms 27764 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN=1e5+5;
const int LOGN=22;
vector<int> g[MAXN];
int dp[MAXN][LOGN];
int tree[MAXN], rtree[MAXN];
int prof[MAXN], gin[MAXN];
int marc[MAXN];
set<int> s;
int n, q, root;
int contv;

void dfs(int cur, int p) {
	for(auto viz : g[cur]) {
		if(viz==p) continue;
		dp[viz][0]=cur;
		gin[cur]++;
		prof[viz]=prof[cur]+1;
		dfs(viz, cur);
	}
}

int pula(int cur) {
	for(int i=LOGN-1; i>=0; i--) {
		if(marc[dp[cur][i]]) cur=dp[cur][i];
	}
	return cur;
}

int main() {
	scanf("%d %d", &n, &q);
	for(int i=1; i<=n; i++) {
		int a; scanf("%d", &a);
		if(a==0) root=i;
		else g[a].push_back(i), g[i].push_back(a);
	}

	dfs(root, root);
	for(int i=1; i<=n; i++) if(!gin[i]) s.insert(i);
	for(int i=1; i<LOGN; i++) {
		for(int j=1; j<=n; j++) dp[j][i]=dp[dp[j][i-1]][i-1];
	}

	while(!s.empty()) {
		int cur= *s.begin();
		int p=dp[cur][0];
		tree[++contv]=cur;
		rtree[cur]=contv;
		gin[p]--;
		if(!gin[p]) s.insert(p);
		s.erase(cur);
	}

	for(int i=1; i<=n; i++) s.insert(i);

	while(q--) {
		int a, x; scanf("%d %d", &a, &x);
		if(a==1) {
			int cur, ind;
			while(x--) {
				ind= *s.begin();
				s.erase(s.begin());
				cur=tree[ind];
				marc[cur]=1;
				// printf("tira %d (%d)\n", cur, ind);
			}
			printf("%d\n", cur);
		}
		else {
			int cur=pula(x);
			int ind=rtree[cur];
			// printf("coloca %d (%d)\n", cur, ind);
			s.insert(ind);
			marc[cur]=0;
			printf("%d\n", prof[x]-prof[cur]);
		}
	}
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:33: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:35:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a; scanf("%d", &a);
          ~~~~~^~~~~~~~~~
ballmachine.cpp:59:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, x; scanf("%d %d", &a, &x);
             ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2944 KB Output isn't correct
2 Execution timed out 1078 ms 16152 KB Time limit exceeded
3 Incorrect 127 ms 15864 KB Output isn't correct
4 Execution timed out 1070 ms 2688 KB Time limit exceeded
5 Incorrect 5 ms 2816 KB Output isn't correct
6 Incorrect 5 ms 2944 KB Output isn't correct
7 Execution timed out 1077 ms 2944 KB Time limit exceeded
8 Execution timed out 1077 ms 2944 KB Time limit exceeded
9 Execution timed out 1078 ms 3456 KB Time limit exceeded
10 Execution timed out 1081 ms 6008 KB Time limit exceeded
11 Execution timed out 1088 ms 15740 KB Time limit exceeded
12 Incorrect 103 ms 15864 KB Output isn't correct
13 Incorrect 184 ms 16140 KB Output isn't correct

Subtask #2
10.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 7672 KB Output is correct
2 Incorrect 342 ms 25148 KB Output isn't correct
3 Correct 190 ms 22004 KB Output is correct
4 Execution timed out 1077 ms 9720 KB Time limit exceeded
5 Execution timed out 1071 ms 9336 KB Time limit exceeded
6 Incorrect 140 ms 9976 KB Output isn't correct
7 Execution timed out 1076 ms 9024 KB Time limit exceeded
8 Correct 46 ms 7672 KB Output is correct
9 Execution timed out 1082 ms 24696 KB Time limit exceeded
10 Incorrect 301 ms 25064 KB Output isn't correct
11 Incorrect 264 ms 25204 KB Output isn't correct
12 Incorrect 301 ms 23560 KB Output isn't correct
13 Correct 178 ms 24184 KB Output is correct
14 Correct 225 ms 22288 KB Output is correct

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 153 ms 13912 KB Output isn't correct
2 Incorrect 385 ms 23984 KB Output isn't correct
3 Correct 190 ms 22620 KB Output is correct
4 Incorrect 256 ms 20472 KB Output isn't correct
5 Incorrect 246 ms 20472 KB Output isn't correct
6 Incorrect 237 ms 20472 KB Output isn't correct
7 Incorrect 213 ms 19576 KB Output isn't correct
8 Correct 162 ms 22392 KB Output is correct
9 Incorrect 281 ms 25208 KB Output isn't correct
10 Incorrect 306 ms 25400 KB Output isn't correct
11 Incorrect 371 ms 25208 KB Output isn't correct
12 Incorrect 367 ms 24004 KB Output isn't correct
13 Correct 366 ms 27764 KB Output is correct
14 Incorrect 354 ms 22868 KB Output isn't correct

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1077 ms 25152 KB Time limit exceeded
2 Incorrect 338 ms 23928 KB Output isn't correct
3 Correct 192 ms 26984 KB Output is correct
4 Execution timed out 1080 ms 25208 KB Time limit exceeded
5 Incorrect 295 ms 25136 KB Output isn't correct
6 Incorrect 230 ms 25192 KB Output isn't correct
7 Incorrect 260 ms 23800 KB Output isn't correct
8 Correct 170 ms 26872 KB Output is correct
9 Correct 143 ms 22004 KB Output is correct