#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 'long long int graphsort(long long 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 'long long int add_k(long long int)':
ballmachine.cpp:54:9: warning: 'lastpos' may be used uninitialized in this function [-Wmaybe-uninitialized]
return lastpos;
^~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
384 KB |
Output is correct |
2 |
Correct |
579 ms |
21724 KB |
Output is correct |
3 |
Correct |
350 ms |
21820 KB |
Output is correct |
4 |
Correct |
3 ms |
256 KB |
Output is correct |
5 |
Correct |
3 ms |
384 KB |
Output is correct |
6 |
Correct |
4 ms |
640 KB |
Output is correct |
7 |
Correct |
5 ms |
640 KB |
Output is correct |
8 |
Correct |
6 ms |
640 KB |
Output is correct |
9 |
Correct |
31 ms |
1664 KB |
Output is correct |
10 |
Correct |
95 ms |
5752 KB |
Output is correct |
11 |
Correct |
526 ms |
21832 KB |
Output is correct |
12 |
Correct |
296 ms |
21752 KB |
Output is correct |
13 |
Correct |
450 ms |
21624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
261 ms |
8780 KB |
Output is correct |
2 |
Correct |
808 ms |
37864 KB |
Output is correct |
3 |
Correct |
335 ms |
32624 KB |
Output is correct |
4 |
Correct |
358 ms |
11904 KB |
Output is correct |
5 |
Correct |
358 ms |
11896 KB |
Output is correct |
6 |
Correct |
322 ms |
11860 KB |
Output is correct |
7 |
Correct |
332 ms |
10360 KB |
Output is correct |
8 |
Correct |
208 ms |
8928 KB |
Output is correct |
9 |
Correct |
746 ms |
38264 KB |
Output is correct |
10 |
Correct |
898 ms |
38008 KB |
Output is correct |
11 |
Correct |
589 ms |
37944 KB |
Output is correct |
12 |
Correct |
780 ms |
34716 KB |
Output is correct |
13 |
Correct |
403 ms |
39196 KB |
Output is correct |
14 |
Correct |
343 ms |
32776 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
392 ms |
19676 KB |
Output is correct |
2 |
Correct |
922 ms |
36472 KB |
Output is correct |
3 |
Correct |
713 ms |
35704 KB |
Output is correct |
4 |
Correct |
556 ms |
30712 KB |
Output is correct |
5 |
Correct |
595 ms |
30456 KB |
Output is correct |
6 |
Correct |
679 ms |
30664 KB |
Output is correct |
7 |
Correct |
645 ms |
29064 KB |
Output is correct |
8 |
Correct |
698 ms |
35636 KB |
Output is correct |
9 |
Correct |
915 ms |
38572 KB |
Output is correct |
10 |
Execution timed out |
1071 ms |
38140 KB |
Time limit exceeded |
11 |
Correct |
994 ms |
38700 KB |
Output is correct |
12 |
Execution timed out |
1037 ms |
36600 KB |
Time limit exceeded |
13 |
Execution timed out |
1043 ms |
44744 KB |
Time limit exceeded |
14 |
Correct |
645 ms |
32988 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
892 ms |
38520 KB |
Output is correct |
2 |
Correct |
962 ms |
36472 KB |
Output is correct |
3 |
Correct |
515 ms |
44396 KB |
Output is correct |
4 |
Correct |
828 ms |
38632 KB |
Output is correct |
5 |
Correct |
895 ms |
38144 KB |
Output is correct |
6 |
Correct |
637 ms |
38396 KB |
Output is correct |
7 |
Correct |
968 ms |
36396 KB |
Output is correct |
8 |
Correct |
474 ms |
44384 KB |
Output is correct |
9 |
Correct |
399 ms |
32736 KB |
Output is correct |