oj.uz

답안 #74670

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
74670 2018-09-06T10:37:36 Z kjain_1810 Ball Machine (BOI13_ballmachine) C++17
100 / 100
 430 ms 107828 KB 
//RESET VALUES OF N TO AVOID RTE :/
#include<bits/stdc++.h>
#define ind(a) scanf("%d", &a)
#define inlld(a) scanf("%lld", &a)
#define pb push_back
#define f first
#define s second
#define ind2(a, b) scanf("%d%d", &a, &b)
#define ind3(a, b, c) scanf("%d%d%d", &a, &b, &c)
#define inlld2(a, b) scanf("%lld%lld", &a, &b)
#define inlld3(a, b, c) scanf("%lld%lld%lld", &a, &b, &c)

using namespace std;

const int N=1e5+5;
const int MOD=1e9+7;
typedef long long ll;
typedef long double ld;	

int power(int a,int b,int m = MOD){
	if(b == 0) return 1;
	if(b == 1) return a;
	int x = power(a,b/2,m)%m;
	x = (x*x)%m;
	if(b%2) return (x*a)%m;
	return x;
}
ll n, q, mini[N], lcapar[N][30], order[N], arr[N];
ll height[N];
vector<ll>adj[N];
set<pair<ll, ll> >ss[N];
void dfs1(ll u, ll par, ll h)
{
	ll anc=1, i=0; 
	ll here=1e9;
	height[u]=h;
	while(anc<=h)
	{
		if(i==0)
			lcapar[u][i]=par;
		else
			lcapar[u][i]=lcapar[lcapar[u][i-1]][i-1];
		anc*=2;
		i++;
	}
	for(auto v:adj[u])
	{
		if(v==par)
			continue;
		dfs1(v, u, h+1);
		here=min(here, min(mini[v], v));
		ss[u].insert({min(mini[v], v), v});
	}
	mini[u]=here;
}
ll tim=1;
void dfs2(ll u)
{
	for(auto v:ss[u])
		dfs2(v.s);
	order[u]=tim++;
}
set<pair<ll, ll> >finalset;
int main()
{
	ll root;
	inlld2(n, q);
	for(ll a=1; a<=n; a++)
	{
		ll p;
		inlld(p);
		if(!p)
			root=a;
		else
		{
			adj[a].pb(p);
			adj[p].pb(a);
		}
	}
	dfs1(root, 0, 0);
	dfs2(root);
	for(ll a=1; a<=n; a++)
		finalset.insert({order[a], a});
	ll ptr=0;
	while(q--)
	{
		ll type, u;
		inlld2(type, u);
		if(type==1)
		{
			ll cnt=0, ans;
			for(auto it:finalset)
			{
				cnt++;
				arr[it.s]=1;
				ans=it.s;
				finalset.erase(it);
				if(cnt==u)
					break;
			}
			printf("%lld\n", ans);
		}
		else
		{
			ll tosub=height[u];
			ll i=log2(height[u])+1;
			while(i>=0)
			{
				if(arr[lcapar[u][i]]==1)
				{
					u=lcapar[u][i];
				}
				else
					i--; //check if correct
			}
			// printf("%lld ", u);
			if(u==0)
				printf("%lld\n", tosub+1);
			else
				printf("%lld\n", tosub-height[u]);
			arr[max((ll)1, u)]=0;
			finalset.insert({order[u], u});
		}
	}
	return 0;
}
//RESET VALUES OF N TO AVOID RTE :/

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:84:5: warning: unused variable 'ptr' [-Wunused-variable]
  ll ptr=0;
     ^~~
ballmachine.cpp:10:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define inlld2(a, b) scanf("%lld%lld", &a, &b)
                      ~~~~~^~~~~~~~~~~~~~~~~~~~
ballmachine.cpp:67:2: note: in expansion of macro 'inlld2'
  inlld2(n, q);
  ^~~~~~
ballmachine.cpp:4:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define inlld(a) scanf("%lld", &a)
                  ~~~~~^~~~~~~~~~~~
ballmachine.cpp:71:3: note: in expansion of macro 'inlld'
   inlld(p);
   ^~~~~
ballmachine.cpp:10:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define inlld2(a, b) scanf("%lld%lld", &a, &b)
                      ~~~~~^~~~~~~~~~~~~~~~~~~~
ballmachine.cpp:88:3: note: in expansion of macro 'inlld2'
   inlld2(type, u);
   ^~~~~~
ballmachine.cpp:81:6: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  dfs2(root);
  ~~~~^~~~~~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 7512 KB Output is correct
2 Correct 255 ms 37616 KB Output is correct
3 Correct 157 ms 37948 KB Output is correct
4 Correct 9 ms 37948 KB Output is correct
5 Correct 9 ms 37948 KB Output is correct
6 Correct 9 ms 37948 KB Output is correct
7 Correct 9 ms 37948 KB Output is correct
8 Correct 10 ms 37948 KB Output is correct
9 Correct 19 ms 37948 KB Output is correct
10 Correct 50 ms 37948 KB Output is correct
11 Correct 264 ms 40000 KB Output is correct
12 Correct 154 ms 40548 KB Output is correct
13 Correct 209 ms 42100 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 70 ms 42100 KB Output is correct
2 Correct 348 ms 64540 KB Output is correct
3 Correct 210 ms 64540 KB Output is correct
4 Correct 131 ms 64540 KB Output is correct
5 Correct 137 ms 64540 KB Output is correct
6 Correct 165 ms 64540 KB Output is correct
7 Correct 128 ms 64540 KB Output is correct
8 Correct 69 ms 64540 KB Output is correct
9 Correct 315 ms 70264 KB Output is correct
10 Correct 364 ms 71864 KB Output is correct
11 Correct 300 ms 73104 KB Output is correct
12 Correct 338 ms 73104 KB Output is correct
13 Correct 227 ms 74352 KB Output is correct
14 Correct 197 ms 74352 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 161 ms 74352 KB Output is correct
2 Correct 380 ms 75696 KB Output is correct
3 Correct 261 ms 75696 KB Output is correct
4 Correct 253 ms 75696 KB Output is correct
5 Correct 273 ms 75696 KB Output is correct
6 Correct 267 ms 75696 KB Output is correct
7 Correct 263 ms 75696 KB Output is correct
8 Correct 280 ms 79136 KB Output is correct
9 Correct 370 ms 85288 KB Output is correct
10 Correct 412 ms 87020 KB Output is correct
11 Correct 430 ms 88284 KB Output is correct
12 Correct 398 ms 88284 KB Output is correct
13 Correct 401 ms 96840 KB Output is correct
14 Correct 327 ms 96840 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 358 ms 96840 KB Output is correct
2 Correct 409 ms 96840 KB Output is correct
3 Correct 260 ms 101212 KB Output is correct
4 Correct 378 ms 101212 KB Output is correct
5 Correct 388 ms 101212 KB Output is correct
6 Correct 314 ms 101212 KB Output is correct
7 Correct 392 ms 101212 KB Output is correct
8 Correct 261 ms 107828 KB Output is correct
9 Correct 205 ms 107828 KB Output is correct