oj.uz

답안 #147846

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
147846 2019-08-31T02:08:00 Z cheetose Ball Machine (BOI13_ballmachine) C++11
100 / 100
 210 ms 24560 KB 
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<queue>
#include<bitset>
#include<string>
#include<stack>
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>
#include<cstring>
#include<complex>
#include<cmath>
#include<iomanip>
#include<numeric>
#include<algorithm>
#include<list>
#include<functional>
#include<cassert>
#define mp make_pair
#define pb push_back
#define X first
#define Y second
#define y0 y12
#define y1 y22
#define INF 987654321987654321
#define PI 3.141592653589793238462643383279502884
#define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
#define fdn(i,a,b,c) for(int (i)=(a);(i)>=(b);(i)-=(c))
#define MEM0(a) memset((a),0,sizeof(a));
#define MEM_1(a) memset((a),-1,sizeof(a));
#define ALL(a) a.begin(),a.end()
#define SYNC ios_base::sync_with_stdio(false);cin.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef double db;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pll;
typedef pair<ld, ld> Pd;
typedef vector<int> Vi;
typedef vector<ll> Vll;
typedef vector<double> Vd;
typedef vector<Pi> VPi;
typedef vector<Pll> VPll;
typedef vector<Pd> VPd;
typedef tuple<int, int, int> iii;
typedef tuple<int,int,int,int> iiii;
typedef tuple<ll, ll, ll> LLL;
typedef vector<iii> Viii;
typedef vector<LLL> VLLL;
typedef complex<double> base;
const ll MOD = 1000000007;
ll POW(ll a, ll b, ll MMM = MOD) {ll ret=1; for(;b;b>>=1,a=(a*a)%MMM)if(b&1)ret=(ret*a)% MMM; return ret; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { if (a == 0 || b == 0)return a + b; return a*(b / gcd(a, b)); }
int dx[] = { 0,1,0,-1,1,1,-1,-1 }, dy[] = { 1,0,-1,0,1,-1,1,-1 };

int n,q,R;
Vi v[100001];
int mn[100001],parent[100001][17];
void dfs1(int N)
{
	mn[N]=N;
	for(int next:v[N])
	{
		parent[next][0]=N;
		dfs1(next);
		mn[N]=min(mn[N],mn[next]);
	}
	sort(ALL(v[N]),[&](int a,int b){
		return mn[a]<mn[b];
	});
}
Vi vv,rv;
bool chk[100001];
void dfs2(int N)
{
	for(int next:v[N])
	{
		dfs2(next);
	}
	vv.pb(N);
}
int tree[262144];
void upd(int node, int S, int E, int k, int dif)
{
	tree[node] += dif;
	if (S == E)return;
	if (k <= (S + E) / 2)upd(node * 2, S, (S + E) / 2, k, dif);
	else upd(node * 2 + 1, (S + E) / 2 + 1, E, k, dif);
}

int find(int node, int S, int E)
{
	if(S==E)return S;
	int M=(S+E)>>1;
	if(tree[node*2]!=M-S+1)return find(node*2,S,M);
	else return find(node*2+1,M+1,E);
}
int go(){
	int t=find(1,0,n-1);
	upd(1,0,n-1,t,1);
	chk[vv[t]]=1;
	return vv[t];
}
int main() {
	MEM_1(parent);
	scanf("%d%d",&n,&q);
	fup(i,0,n-1,1)
	{
		int x;
		scanf("%d",&x);
		if(x)v[x-1].pb(i);
		else R=i;
	}
	dfs1(R);dfs2(R);
	fup(j,0,15,1)
		fup(i,0,n-1,1)
	{
		if(parent[i][j]!=-1)
		{
			parent[i][j+1]=parent[parent[i][j]][j];
		}
	}
	rv.resize(n);
	fup(i,0,n-1,1)rv[vv[i]]=i;
	while(q--)
	{
		int o,x;
		scanf("%d%d",&o,&x);
		if(o==1)
		{
			int ans=-1;
			while(x--)ans=go();
			printf("%d\n",ans+1);
		}
		else
		{
			int ans=0;
			int now=x-1;
			fdn(i,16,0,1)
			{
				if(parent[now][i]!=-1 && chk[parent[now][i]])
				{
					now=parent[now][i];
					ans+=(1<<i);
				}
			}
			chk[now]=0;
			upd(1,0,n-1,rv[now],-1);
			printf("%d\n",ans);
		}
	}
}

Compilation message

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

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 9468 KB Output is correct
2 Correct 118 ms 13144 KB Output is correct
3 Correct 80 ms 12664 KB Output is correct
4 Correct 10 ms 9336 KB Output is correct
5 Correct 10 ms 9392 KB Output is correct
6 Correct 10 ms 9336 KB Output is correct
7 Correct 10 ms 9336 KB Output is correct
8 Correct 11 ms 9336 KB Output is correct
9 Correct 16 ms 9592 KB Output is correct
10 Correct 32 ms 10232 KB Output is correct
11 Correct 116 ms 13048 KB Output is correct
12 Correct 77 ms 12636 KB Output is correct
13 Correct 109 ms 12792 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 12408 KB Output is correct
2 Correct 155 ms 18852 KB Output is correct
3 Correct 98 ms 13452 KB Output is correct
4 Correct 84 ms 12792 KB Output is correct
5 Correct 79 ms 12676 KB Output is correct
6 Correct 74 ms 12408 KB Output is correct
7 Correct 77 ms 12048 KB Output is correct
8 Correct 51 ms 12536 KB Output is correct
9 Correct 162 ms 19316 KB Output is correct
10 Correct 163 ms 18844 KB Output is correct
11 Correct 148 ms 18412 KB Output is correct
12 Correct 155 ms 16756 KB Output is correct
13 Correct 114 ms 21744 KB Output is correct
14 Correct 97 ms 13404 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 84 ms 14580 KB Output is correct
2 Correct 189 ms 17396 KB Output is correct
3 Correct 127 ms 21356 KB Output is correct
4 Correct 121 ms 17524 KB Output is correct
5 Correct 112 ms 17140 KB Output is correct
6 Correct 122 ms 17096 KB Output is correct
7 Correct 112 ms 15476 KB Output is correct
8 Correct 139 ms 21280 KB Output is correct
9 Correct 178 ms 19764 KB Output is correct
10 Correct 186 ms 19388 KB Output is correct
11 Correct 170 ms 19392 KB Output is correct
12 Correct 175 ms 17380 KB Output is correct
13 Correct 190 ms 24560 KB Output is correct
14 Correct 138 ms 14800 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 187 ms 19500 KB Output is correct
2 Correct 169 ms 17176 KB Output is correct
3 Correct 131 ms 23116 KB Output is correct
4 Correct 179 ms 19480 KB Output is correct
5 Correct 210 ms 18908 KB Output is correct
6 Correct 147 ms 18444 KB Output is correct
7 Correct 167 ms 17136 KB Output is correct
8 Correct 128 ms 23152 KB Output is correct
9 Correct 97 ms 13376 KB Output is correct