#include <bits/stdc++.h>
//#define int long long
#define P(x) do {if(debug) cout << x << endl;} while(false)
#define H(x) P(#x << ": " << x)
#define FR(i, a, b) for(int i = (a); i < (b); ++i)
#define F(i, n) FR(i, 0, n)
#define DR(i, a, b) for(int i = (b); i --> (a);)
#define D(i, n) DR(i, 0, n)
#define S(s) (int)(s).size()
#define ALL(x) (x).begin(), (x).end()
#define MI(x, a) (x) = min(x, a)
#define MA(x, a) (x) = max(x, a)
#define V vector
#define pb push_back
#define mp make_pair
using namespace std;
const bool debug = 0;
vector<vector<int> > graph;
vector<int> order, parent, depth;
set<pair<int,int> > notfilled;
int N, n, Q, q, root;
vector<bool> filled;
vector<vector<int> > memo;
int graphsort(int u){
vector<pair<int,int> > vv;
for(int v : graph[u]){
vv.push_back(mp(graphsort(v), v));
}
sort(vv.begin(), vv.end());
int mi = u;
F(i,graph[u].size()){
mi = min(mi, vv[i].first);
graph[u][i] = vv[i].second;
}
return mi;
}
void dfs(int u, int& i, int d){
for(int v : graph[u]){
dfs(v, i, d+1);
}
depth[u]=d;
P("insert "<<i<<" "<<u);
notfilled.insert(mp(i, u));
order[u]=i++;
}
int add_k(int k){
int lastpos;
F(i, k){
lastpos= (*notfilled.begin()).second;
P(i<<" "<<lastpos);
filled[lastpos] = true;
notfilled.erase(notfilled.begin());
}
return lastpos;
}
int f(int u, int p2){
if(p2==0) return parent[u];
if(memo[u][p2] != -1) return memo[u][p2];
return memo[u][p2] = f(f(u, p2-1), p2-1);
}
int remove(int u){
int v = u;
for(int bs = 19; bs>=0; bs--){
if(filled[f(v, bs)]){
v = f(v,bs);
P(v<<" is too low");
}
}
P(v<<" is highest ");
filled[v]=false;
notfilled.insert(mp(order[v], v));
return depth[u]-depth[v];
}
signed main() {
ios_base::sync_with_stdio(true);
cin.tie(0);
cin>>N>>Q;
n = N; q = Q;
graph.resize(n);
parent.resize(n);
order.resize(n);
depth.resize(n);
filled.resize(n, false);
memo.resize(n+10, vector<int>(21, -1));
F(i, N){
int a;
cin>>a;
a--;
parent[i]=a;
if(a==-1){
root = i;
parent[i]=i;
continue;
}
graph[a].push_back(i);
}
graphsort(root);
int xxxx = 0;
dfs(root, xxxx, 0);
F(i, q){
P("Hellooo");
int t;
cin>>t;
int a;
cin>>a;
P("Hello aaaa");
if(t==1){
cout<<add_k(a)+1<<endl;
}
else{
cout<<remove(a-1)<<endl;
}
}
return 0;
}
Compilation message
ballmachine.cpp: In function 'int graphsort(int)':
ballmachine.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define FR(i, a, b) for(int i = (a); i < (b); ++i)
^
ballmachine.cpp:6:17: note: in expansion of macro 'FR'
#define F(i, n) FR(i, 0, n)
^~
ballmachine.cpp:31:2: note: in expansion of macro 'F'
F(i,graph[u].size()){
^
ballmachine.cpp: In function 'int add_k(int)':
ballmachine.cpp:54:9: warning: 'lastpos' may be used uninitialized in this function [-Wmaybe-uninitialized]
return lastpos;
^~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
500 ms |
14872 KB |
Output is correct |
3 |
Correct |
298 ms |
14808 KB |
Output is correct |
4 |
Correct |
3 ms |
384 KB |
Output is correct |
5 |
Correct |
4 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
512 KB |
Output is correct |
7 |
Correct |
5 ms |
512 KB |
Output is correct |
8 |
Correct |
8 ms |
512 KB |
Output is correct |
9 |
Correct |
33 ms |
1280 KB |
Output is correct |
10 |
Correct |
87 ms |
3932 KB |
Output is correct |
11 |
Correct |
490 ms |
14704 KB |
Output is correct |
12 |
Correct |
295 ms |
14872 KB |
Output is correct |
13 |
Correct |
414 ms |
14816 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
223 ms |
6508 KB |
Output is correct |
2 |
Correct |
817 ms |
27276 KB |
Output is correct |
3 |
Correct |
325 ms |
21936 KB |
Output is correct |
4 |
Correct |
313 ms |
8568 KB |
Output is correct |
5 |
Correct |
341 ms |
8440 KB |
Output is correct |
6 |
Correct |
291 ms |
8656 KB |
Output is correct |
7 |
Correct |
318 ms |
7288 KB |
Output is correct |
8 |
Correct |
182 ms |
6612 KB |
Output is correct |
9 |
Correct |
651 ms |
27744 KB |
Output is correct |
10 |
Correct |
837 ms |
27124 KB |
Output is correct |
11 |
Correct |
564 ms |
27324 KB |
Output is correct |
12 |
Correct |
634 ms |
24316 KB |
Output is correct |
13 |
Correct |
370 ms |
29432 KB |
Output is correct |
14 |
Correct |
314 ms |
21884 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
338 ms |
14168 KB |
Output is correct |
2 |
Correct |
890 ms |
25208 KB |
Output is correct |
3 |
Correct |
665 ms |
26848 KB |
Output is correct |
4 |
Correct |
498 ms |
22432 KB |
Output is correct |
5 |
Correct |
540 ms |
22012 KB |
Output is correct |
6 |
Correct |
573 ms |
21880 KB |
Output is correct |
7 |
Correct |
529 ms |
19992 KB |
Output is correct |
8 |
Correct |
630 ms |
26776 KB |
Output is correct |
9 |
Correct |
758 ms |
27840 KB |
Output is correct |
10 |
Correct |
944 ms |
27516 KB |
Output is correct |
11 |
Execution timed out |
1040 ms |
27512 KB |
Time limit exceeded |
12 |
Execution timed out |
1022 ms |
25192 KB |
Time limit exceeded |
13 |
Execution timed out |
1059 ms |
33656 KB |
Time limit exceeded |
14 |
Correct |
552 ms |
22104 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
732 ms |
28008 KB |
Output is correct |
2 |
Correct |
833 ms |
25212 KB |
Output is correct |
3 |
Correct |
406 ms |
33180 KB |
Output is correct |
4 |
Correct |
698 ms |
27896 KB |
Output is correct |
5 |
Correct |
710 ms |
27512 KB |
Output is correct |
6 |
Correct |
539 ms |
27532 KB |
Output is correct |
7 |
Correct |
779 ms |
25208 KB |
Output is correct |
8 |
Correct |
376 ms |
33264 KB |
Output is correct |
9 |
Correct |
301 ms |
21864 KB |
Output is correct |