oj.uz

Submission #110490

# Submission time Handle Problem Language Result Execution time Memory
110490 2019-05-11T00:14:13 Z wilwxk Ball Machine (BOI13_ballmachine) C++11
8.57143 / 100
 1000 ms 21368 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 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(q--) {
		int a, x; scanf("%d %d", &a, &x);
		if(a==1) {
			int cur, p;
			while(x--) {
				cur= *s.begin();
				p=dp[cur][0];
				s.erase(s.begin());
				marc[cur]=1;
				gin[p]--;
				if(!gin[p]) s.insert(p);
			}
			printf("%d\n", cur);
		}
		else {
			int cur=pula(x);
			int p=dp[cur][0];
			marc[cur]=0;
			gin[p]++;
			s.erase(p);
			printf("%d\n", prof[x]-prof[cur]);
		}
	}
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:32: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:34: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:46: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 Execution timed out 1067 ms 2688 KB Time limit exceeded
2 Execution timed out 1067 ms 13304 KB Time limit exceeded
3 Incorrect 102 ms 13560 KB Output isn't correct
4 Execution timed out 1068 ms 2688 KB Time limit exceeded
5 Execution timed out 1073 ms 2816 KB Time limit exceeded
6 Incorrect 5 ms 2816 KB Output isn't correct
7 Execution timed out 1063 ms 2816 KB Time limit exceeded
8 Execution timed out 1075 ms 2816 KB Time limit exceeded
9 Execution timed out 1073 ms 3328 KB Time limit exceeded
10 Execution timed out 1066 ms 5468 KB Time limit exceeded
11 Execution timed out 1074 ms 13304 KB Time limit exceeded
12 Incorrect 121 ms 13600 KB Output isn't correct
13 Execution timed out 1073 ms 13244 KB Time limit exceeded

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1052 ms 6144 KB Time limit exceeded
2 Execution timed out 1075 ms 20344 KB Time limit exceeded
3 Incorrect 132 ms 19444 KB Output isn't correct
4 Execution timed out 1065 ms 8136 KB Time limit exceeded
5 Execution timed out 1067 ms 8192 KB Time limit exceeded
6 Execution timed out 1068 ms 8312 KB Time limit exceeded
7 Execution timed out 1072 ms 7672 KB Time limit exceeded
8 Execution timed out 1051 ms 6144 KB Time limit exceeded
9 Execution timed out 1071 ms 19704 KB Time limit exceeded
10 Execution timed out 1054 ms 20216 KB Time limit exceeded
11 Execution timed out 1072 ms 20348 KB Time limit exceeded
12 Execution timed out 1072 ms 18808 KB Time limit exceeded
13 Execution timed out 1088 ms 18300 KB Time limit exceeded
14 Incorrect 131 ms 19444 KB Output isn't correct

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 94 ms 11640 KB Output isn't correct
2 Incorrect 230 ms 19436 KB Output isn't correct
3 Correct 193 ms 17528 KB Output is correct
4 Incorrect 150 ms 16504 KB Output isn't correct
5 Incorrect 172 ms 16936 KB Output isn't correct
6 Incorrect 169 ms 17016 KB Output isn't correct
7 Incorrect 140 ms 16040 KB Output isn't correct
8 Correct 144 ms 17656 KB Output is correct
9 Incorrect 285 ms 20208 KB Output isn't correct
10 Incorrect 263 ms 20596 KB Output isn't correct
11 Incorrect 231 ms 20572 KB Output isn't correct
12 Incorrect 234 ms 19392 KB Output isn't correct
13 Correct 228 ms 21368 KB Output is correct
14 Incorrect 216 ms 19504 KB Output isn't correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1062 ms 19580 KB Time limit exceeded
2 Execution timed out 1075 ms 19296 KB Time limit exceeded
3 Execution timed out 1081 ms 20472 KB Time limit exceeded
4 Execution timed out 1067 ms 19832 KB Time limit exceeded
5 Execution timed out 1063 ms 20388 KB Time limit exceeded
6 Execution timed out 1066 ms 20344 KB Time limit exceeded
7 Execution timed out 1079 ms 19200 KB Time limit exceeded
8 Execution timed out 1074 ms 20344 KB Time limit exceeded
9 Incorrect 155 ms 19528 KB Output isn't correct