oj.uz

Submission #112513

# Submission time Handle Problem Language Result Execution time Memory
112513 2019-05-20T11:28:11 Z Kastanda Ball Machine (BOI13_ballmachine) C++11
100 / 100
 332 ms 26076 KB 
#include<bits/stdc++.h>
using namespace std;
const int N = 100005, LG = 18;
int n, q, ts, P[N], H[N], rev[N], mn[N], par[N][LG], M[N];
vector < int > Adj[N];
set < int > S;
bool CMP(int i, int j)
{
	return (mn[i] < mn[j]);
}
void DFS(int v)
{
	mn[v] = v;
	for (int i = 1; i < LG; i++)
		par[v][i] = par[par[v][i - 1]][i - 1];
	for (int &u : Adj[v])
	{
		H[u] = H[v] + 1;
		par[u][0] = v;
		DFS(u);
		mn[v] = min(mn[v], mn[u]);
	}
}
void DFS2(int v)
{
	for (int &u : Adj[v])
		DFS2(u);
	P[v] = ts ++;
	rev[P[v]] = v;
	S.insert(P[v]);
}
inline int Get(int v)
{
	for (int i = LG - 1; ~ i; i --)
		if (M[par[v][i]])
			v = par[v][i];
	return (v);
}
int main()
{
	scanf("%d%d", &n, &q);
	for (int i = 1, p; i <= n; i++)
		scanf("%d", &p), Adj[p].push_back(i);
	DFS(0);
	for (int i = 0; i <= n; i++)
		sort(Adj[i].begin(), Adj[i].end(), CMP);
	DFS2(0);
	for (; q; q --)
	{
		int tp, v;
		scanf("%d%d", &tp, &v);
		if (tp == 1)
		{
			int u;
			for (; v; v --)
			{
				u = rev[*S.begin()];
				S.erase(S.begin());
				M[u] = 1;
			}
			printf("%d\n", u);
		}
		else
		{
			int u = Get(v);
			M[u] = 0;
			S.insert(P[u]);
			printf("%d\n", H[v] - H[u]);
		}
	}
	return 0;
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:41: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:43:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &p), Adj[p].push_back(i);
   ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &tp, &v);
   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 176 ms 14072 KB Output is correct
3 Correct 89 ms 13816 KB Output is correct
4 Correct 3 ms 2688 KB Output is correct
5 Correct 4 ms 2816 KB Output is correct
6 Correct 4 ms 2816 KB Output is correct
7 Correct 5 ms 2816 KB Output is correct
8 Correct 5 ms 2816 KB Output is correct
9 Correct 10 ms 3328 KB Output is correct
10 Correct 33 ms 5480 KB Output is correct
11 Correct 205 ms 14072 KB Output is correct
12 Correct 94 ms 13876 KB Output is correct
13 Correct 143 ms 14104 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 7340 KB Output is correct
2 Correct 253 ms 22236 KB Output is correct
3 Correct 122 ms 18420 KB Output is correct
4 Correct 100 ms 9180 KB Output is correct
5 Correct 113 ms 8952 KB Output is correct
6 Correct 88 ms 8956 KB Output is correct
7 Correct 101 ms 8412 KB Output is correct
8 Correct 42 ms 7416 KB Output is correct
9 Correct 228 ms 22700 KB Output is correct
10 Correct 276 ms 22264 KB Output is correct
11 Correct 210 ms 22220 KB Output is correct
12 Correct 262 ms 20792 KB Output is correct
13 Correct 146 ms 22904 KB Output is correct
14 Correct 119 ms 18448 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 12768 KB Output is correct
2 Correct 288 ms 21192 KB Output is correct
3 Correct 183 ms 21180 KB Output is correct
4 Correct 178 ms 18524 KB Output is correct
5 Correct 185 ms 18268 KB Output is correct
6 Correct 201 ms 18296 KB Output is correct
7 Correct 193 ms 17408 KB Output is correct
8 Correct 165 ms 21084 KB Output is correct
9 Correct 308 ms 23048 KB Output is correct
10 Correct 332 ms 22392 KB Output is correct
11 Correct 298 ms 22528 KB Output is correct
12 Correct 284 ms 21240 KB Output is correct
13 Correct 315 ms 26076 KB Output is correct
14 Correct 265 ms 19444 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 22904 KB Output is correct
2 Correct 277 ms 21304 KB Output is correct
3 Correct 173 ms 25464 KB Output is correct
4 Correct 247 ms 22888 KB Output is correct
5 Correct 277 ms 22520 KB Output is correct
6 Correct 206 ms 22392 KB Output is correct
7 Correct 267 ms 21368 KB Output is correct
8 Correct 161 ms 25464 KB Output is correct
9 Correct 118 ms 18548 KB Output is correct