oj.uz

답안 #882546

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
882546 2023-12-03T10:55:11 Z arashMLG Ball Machine (BOI13_ballmachine) C++17
100 / 100
 95 ms 64704 KB 
#include<bits/stdc++.h>
#ifdef LOCAL
#include "Essentials/algo/debug.h"
#else
#define debug(...) 69
#endif
using namespace std;

typedef long long     ll;
typedef pair<int,int> pii;

const int N = 5e5 + 23;
const int LOG = 20;
const ll inf = 1e18;

#define F           first
#define S           second
#define pb          push_back
#define kill(x)     cout<<x<<endl, exit(0);
#define all(x)      x.begin(),x.end()
#define sz(x)       (int)x.size()
#define lc          (v << 1)
#define rc          ((v<<1) |1)

int n,q;
int val[N],ft[N];
int timer;
priority_queue<pii, vector<pii> , greater<> > pq;
vector<int> G[N];
int up[LOG][N];
bool is[N];

void dfs1(int v) {
	val[v] = v;
	for(int u : G[v]) {
		dfs1(u);
		val[v] = min(val[v],val[u]);
	}
}

void dfs2(int v) {
	sort(all(G[v]) , [&] (int x,int y) { return val[x] < val[y];});
	for(int u : G[v]) {
		dfs2(u);
	}
	ft[v] = timer ++;
}

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(false);
	cin>>n>>q;
	int root=-1;
	for(int i = 1; i <= n; i ++) {
		int p; cin>>p;
		up[0][i] = p;
		if(p == 0) root = i;
		else G[p].pb(i);
	}
	for(int i = 1; i< LOG; i++) 
		for(int v= 1; v <= n ; v ++)
			up[i][v] = up[i-1][up[i-1][v]];
	dfs1(root);
	dfs2(root);
	for(int i = 1; i<= n ; i ++) {
		pq.push({ ft[i],i});
	}
	while(q--) {
		int k,x; cin>>k>>x;
		if(k == 1) {
			debug("BEGIN",1);
			int ans=-1;
			debug(x);
			while(x--) {
				int v = pq.top().S; pq.pop();
				debug(v);
				is[v] = true;
				ans = v;
			}	
			cout<<ans << '\n'; debug("END",1);	
		} else {
			debug("BEGIN",2);
			int ans=0;
			debug(x);
			for(int i = LOG-1; i >= 0 ; i--) {
				if(is[up[i][x]])
					ans += (1 << i), x = up[i][x];
			}
			debug(x);
			is[x] = false;
			pq.push({ft[x],x});
			cout<<ans << '\n';  debug("END",2);
		}
	}
	return 0;
}

Compilation message

ballmachine.cpp: In function 'int32_t main()':
ballmachine.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 69
      |                    ^~
ballmachine.cpp:70:4: note: in expansion of macro 'debug'
   70 |    debug("BEGIN",1);
      |    ^~~~~
ballmachine.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 69
      |                    ^~
ballmachine.cpp:72:4: note: in expansion of macro 'debug'
   72 |    debug(x);
      |    ^~~~~
ballmachine.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 69
      |                    ^~
ballmachine.cpp:75:5: note: in expansion of macro 'debug'
   75 |     debug(v);
      |     ^~~~~
ballmachine.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 69
      |                    ^~
ballmachine.cpp:79:23: note: in expansion of macro 'debug'
   79 |    cout<<ans << '\n'; debug("END",1);
      |                       ^~~~~
ballmachine.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 69
      |                    ^~
ballmachine.cpp:81:4: note: in expansion of macro 'debug'
   81 |    debug("BEGIN",2);
      |    ^~~~~
ballmachine.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 69
      |                    ^~
ballmachine.cpp:83:4: note: in expansion of macro 'debug'
   83 |    debug(x);
      |    ^~~~~
ballmachine.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 69
      |                    ^~
ballmachine.cpp:88:4: note: in expansion of macro 'debug'
   88 |    debug(x);
      |    ^~~~~
ballmachine.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 69
      |                    ^~
ballmachine.cpp:91:24: note: in expansion of macro 'debug'
   91 |    cout<<ans << '\n';  debug("END",2);
      |                        ^~~~~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 53848 KB Output is correct
2 Correct 63 ms 56784 KB Output is correct
3 Correct 38 ms 56812 KB Output is correct
4 Correct 7 ms 53596 KB Output is correct
5 Correct 7 ms 53596 KB Output is correct
6 Correct 7 ms 53848 KB Output is correct
7 Correct 8 ms 53700 KB Output is correct
8 Correct 8 ms 53852 KB Output is correct
9 Correct 11 ms 53932 KB Output is correct
10 Correct 18 ms 54536 KB Output is correct
11 Correct 55 ms 56760 KB Output is correct
12 Correct 38 ms 56760 KB Output is correct
13 Correct 64 ms 56816 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 56272 KB Output is correct
2 Correct 72 ms 60624 KB Output is correct
3 Correct 43 ms 57408 KB Output is correct
4 Correct 38 ms 56528 KB Output is correct
5 Correct 38 ms 56268 KB Output is correct
6 Correct 38 ms 56280 KB Output is correct
7 Correct 39 ms 55772 KB Output is correct
8 Correct 27 ms 56280 KB Output is correct
9 Correct 73 ms 61212 KB Output is correct
10 Correct 80 ms 60968 KB Output is correct
11 Correct 68 ms 60804 KB Output is correct
12 Correct 66 ms 59452 KB Output is correct
13 Correct 51 ms 63176 KB Output is correct
14 Correct 44 ms 57488 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 57552 KB Output is correct
2 Correct 75 ms 59600 KB Output is correct
3 Correct 66 ms 62156 KB Output is correct
4 Correct 55 ms 59684 KB Output is correct
5 Correct 54 ms 59240 KB Output is correct
6 Correct 54 ms 59340 KB Output is correct
7 Correct 53 ms 58192 KB Output is correct
8 Correct 64 ms 62172 KB Output is correct
9 Correct 74 ms 61384 KB Output is correct
10 Correct 83 ms 61128 KB Output is correct
11 Correct 80 ms 60876 KB Output is correct
12 Correct 79 ms 59836 KB Output is correct
13 Correct 95 ms 64704 KB Output is correct
14 Correct 68 ms 57892 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 61388 KB Output is correct
2 Correct 76 ms 59668 KB Output is correct
3 Correct 55 ms 64248 KB Output is correct
4 Correct 84 ms 61352 KB Output is correct
5 Correct 77 ms 60880 KB Output is correct
6 Correct 69 ms 60876 KB Output is correct
7 Correct 76 ms 59752 KB Output is correct
8 Correct 69 ms 64216 KB Output is correct
9 Correct 43 ms 57448 KB Output is correct