#include<bits/stdc++.h>
using namespace std ;
#define maxn 200009
#define ll long long
#define fi first
#define se second
#define pb push_back
#define left id<<1
#define right id<<1|1
#define _lower(x) lower_bound(v.begin(),v.end(),x)-v.begin()+1
#define TIME (1.0*clock()/TIME_PERS_SEC)
#define re exit(0);
const int mod = 1e9+7 ;
const int INF = 1e9 ;
const int LOG = 18 ;
typedef vector<int> vi ;
typedef pair<int,int> pii ;
typedef vector<pii> vii ;
void add ( int &a , int b )
{
a += b ;
if ( a >= mod ) a -= mod ;
if ( a < 0 ) a += mod ;
}
template < typename T > void chkmin ( T &a , T b ) { if ( a > b ) a = b ;}
template < typename T > void chkmax ( T &a , T b ) { if ( a < b ) a = b ;}
void rf ()
{
freopen ("bai1.inp","r",stdin) ;
}
mt19937 rng (time(0)) ;
int _pow ( int a , int n )
{
if ( n == 0 ) return 1 ;
int res = _pow (a,n/2) ;
if ( n % 2 ) return 1ll*res*res%mod*a%mod ;
else return 1ll*res*res%mod ;
}
int n , nq , root ;
vi adjList [maxn] ;
vi child [maxn] ;
int dp [maxn] ;
int par [maxn][20] , dep [maxn] ;
void dfs ( int u )
{
dp [u] = u ;
for ( auto v : adjList [u] )
{
if ( v == par [u][0] ) continue ;
par [v][0] = u ; dep [v] = dep [u] + 1 ;
for ( int i = 1 ; i <= LOG ; i ++ ) par [v][i] = par[par[v][i-1]][i-1] ;
dfs (v) ;
chkmin (dp[u],dp[v]) ;
child [u] . pb (v) ;
}
}
bool cmp ( int u , int v )
{
return dp [u] < dp [v] ;
}
int ver1 [maxn] , ver2 [maxn] ;
void find_order ( int u )
{
static int cnt = 0 ;
for ( auto v : child [u] ) find_order (v) ;
ver1 [++cnt] = u ;
ver2 [u] = cnt ;
}
int have_ball [maxn] ;
int T [maxn*4] ;
void update ( int id , int l , int r , int pos , int w )
{
if ( l > pos || r < pos ) return ;
if ( l == r )
{
T [id] = w ;
return ;
}
int mid = (l+r)/2 ;
update (left,l,mid,pos,w) ;
update (right,mid+1,r,pos,w) ;
T [id] = min (T[left],T[right]) ;
}
int get ( int id , int l , int r )
{
if ( l == r ) return l ;
int mid = (l+r)/2 ;
if ( T [left] == 0 ) return get (left,l,mid) ;
else return get (right,mid+1,r) ;
}
int jump ( int x , int h )
{
for ( int i = LOG ; i >= 0 ; i -- ) if ( h >> i & 1 ) x = par [x][i] ;
return x ;
}
int main ()
{
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// rf () ;
cin >> n >> nq ;
for ( int i = 1 ; i <= n ; i ++ )
{
int x ; cin >> x ;
if ( x == 0 ) root = i ;
else
{
adjList [x] . pb (i) ;
adjList [i] . pb (x) ;
}
}
dfs (root) ;
for ( int i = 1 ; i <= n ; i ++ ) sort (child[i].begin(),child[i].end(),cmp) ;
find_order (root) ;
while ( nq -- )
{
int op , x ; cin >> op >> x ;
if ( op == 1 )
{
int pos ;
while ( x -- )
{
pos = get (1,1,n) ;
update (1,1,n,pos,1) ;
have_ball [ver1[pos]] = 1 ;
}
cout << ver1[pos] << "\n" ;
}
else
{
int l = 0 , r = dep [x] , res;
while ( l <= r )
{
int mid = (l+r)/2 ;
int parent = jump (x,mid) ;
if ( have_ball [parent] == true ) l = mid+1 , res = mid ;
else r = mid-1 ;
}
int parent = jump (x,res) ;
have_ball [parent] = 0 ;
update (1,1,n,ver2[parent],0) ;
cout << res << "\n" ;
}
}
}
Compilation message
ballmachine.cpp: In function 'void rf()':
ballmachine.cpp:34:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
34 | freopen ("bai1.inp","r",stdin) ;
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:106:45: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
106 | for ( int i = LOG ; i >= 0 ; i -- ) if ( h >> i & 1 ) x = par [x][i] ;
| ~~^~~~
ballmachine.cpp:148:30: note: 'res' was declared here
148 | int l = 0 , r = dep [x] , res;
| ^~~
ballmachine.cpp:144:25: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
144 | cout << ver1[pos] << "\n" ;
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
9820 KB |
Output is correct |
2 |
Correct |
125 ms |
21124 KB |
Output is correct |
3 |
Correct |
65 ms |
20492 KB |
Output is correct |
4 |
Correct |
5 ms |
9816 KB |
Output is correct |
5 |
Correct |
5 ms |
9820 KB |
Output is correct |
6 |
Correct |
5 ms |
9816 KB |
Output is correct |
7 |
Correct |
5 ms |
10076 KB |
Output is correct |
8 |
Correct |
5 ms |
10068 KB |
Output is correct |
9 |
Correct |
12 ms |
10604 KB |
Output is correct |
10 |
Correct |
25 ms |
12636 KB |
Output is correct |
11 |
Correct |
102 ms |
21012 KB |
Output is correct |
12 |
Correct |
62 ms |
20308 KB |
Output is correct |
13 |
Correct |
99 ms |
20564 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
48 ms |
15184 KB |
Output is correct |
2 |
Correct |
221 ms |
31660 KB |
Output is correct |
3 |
Correct |
73 ms |
25056 KB |
Output is correct |
4 |
Correct |
103 ms |
16812 KB |
Output is correct |
5 |
Correct |
104 ms |
16884 KB |
Output is correct |
6 |
Correct |
102 ms |
16720 KB |
Output is correct |
7 |
Correct |
93 ms |
15528 KB |
Output is correct |
8 |
Correct |
48 ms |
15192 KB |
Output is correct |
9 |
Correct |
196 ms |
31944 KB |
Output is correct |
10 |
Correct |
256 ms |
31796 KB |
Output is correct |
11 |
Correct |
202 ms |
31060 KB |
Output is correct |
12 |
Correct |
197 ms |
28920 KB |
Output is correct |
13 |
Correct |
127 ms |
33344 KB |
Output is correct |
14 |
Correct |
73 ms |
25040 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
87 ms |
21144 KB |
Output is correct |
2 |
Correct |
273 ms |
30028 KB |
Output is correct |
3 |
Correct |
178 ms |
32080 KB |
Output is correct |
4 |
Correct |
159 ms |
27728 KB |
Output is correct |
5 |
Correct |
190 ms |
27564 KB |
Output is correct |
6 |
Correct |
176 ms |
27424 KB |
Output is correct |
7 |
Correct |
142 ms |
25464 KB |
Output is correct |
8 |
Correct |
204 ms |
32252 KB |
Output is correct |
9 |
Correct |
200 ms |
32416 KB |
Output is correct |
10 |
Correct |
270 ms |
32200 KB |
Output is correct |
11 |
Correct |
240 ms |
32084 KB |
Output is correct |
12 |
Correct |
226 ms |
29784 KB |
Output is correct |
13 |
Correct |
313 ms |
38264 KB |
Output is correct |
14 |
Correct |
120 ms |
26828 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
268 ms |
32236 KB |
Output is correct |
2 |
Correct |
246 ms |
29520 KB |
Output is correct |
3 |
Correct |
123 ms |
36392 KB |
Output is correct |
4 |
Correct |
239 ms |
32336 KB |
Output is correct |
5 |
Correct |
275 ms |
31528 KB |
Output is correct |
6 |
Correct |
213 ms |
30968 KB |
Output is correct |
7 |
Correct |
247 ms |
29556 KB |
Output is correct |
8 |
Correct |
129 ms |
36324 KB |
Output is correct |
9 |
Correct |
72 ms |
25116 KB |
Output is correct |