| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 283239 | 2020-08-25T11:54:30 Z | AKaan37 | Ball Machine (BOI13_ballmachine) | C++17 | 1000 ms | 30072 KB |
//Bismillahirrahmanirrahim
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█▄█
//█─█─█▄─█▄─█─█─█─█
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx2")
#include <bits/stdc++.h>
using namespace std;
typedef long long lo;
typedef pair< lo,lo > PII;
#define fi first
#define se second
#define mp make_pair
#define endl "\n"
#define int long long
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)
const lo inf = 1000000000000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 500005;
const lo mod = 1000000007;
int n,m,b[li],a[li],k,flag,t,vis[li],root,par[li][LOG],last,mini[li];
int cev;
multiset<PII> st;
string s;
vector<int> v;
inline void build_lca(){
for(int i=1;i<=17;i++){
for(int j=1;j<=n;j++)par[j][i]=par[par[j][i-1]][i-1];
}
}
int32_t main(void){
scanf("%lld %lld",&n,&t);
FOR{
int x;
scanf("%lld",&x);
if(x==0){
root=x;
}
else{
vis[x]++;
par[i][0]=x;
}
}
FOR{
if(vis[i]==0)st.insert({i,i});
mini[i]=i;
}
build_lca();
vis[0]=1000000;
while(t--){
int type;
scanf("%lld",&type);
if(type==1){
scanf("%lld",&k);
while(k){
k--;
auto it=st.begin();
PII p=*it;
last=p.se;
//~ if(last==212)cout<<k<<"**\n";
//~ cout<<last<<endl;
vis[par[p.se][0]]--;
if(vis[par[p.se][0]]==0){mini[par[p.se][0]]=min(par[p.se][0],p.fi);st.insert({min(par[p.se][0],p.fi),par[p.se][0]});}
st.erase(it);
}
printf("%lld\n",last);
continue;
}
int x;
scanf("%lld",&x);
//~ int y=x;
cev=0;
for(int i=17;i>=0;i--){
if(vis[par[x][i]] || st.find({mini[par[x][i]],par[x][i]})!=st.end())continue;
x=par[x][i];
cev+=(1<<i);
}
if(st.find({mini[par[x][0]],par[x][0]})!=st.end()){st.erase(st.find({mini[par[x][0]],par[x][0]}));}
vis[par[x][0]]++;
st.insert({mini[x],x});
printf("%lld\n",cev);
}
return 0;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 1 ms | 384 KB | Output isn't correct |
| 2 | Execution timed out | 1059 ms | 19648 KB | Time limit exceeded |
| 3 | Incorrect | 84 ms | 19832 KB | Output isn't correct |
| 4 | Execution timed out | 1086 ms | 384 KB | Time limit exceeded |
| 5 | Incorrect | 1 ms | 384 KB | Output isn't correct |
| 6 | Incorrect | 1 ms | 640 KB | Output isn't correct |
| 7 | Execution timed out | 1082 ms | 640 KB | Time limit exceeded |
| 8 | Incorrect | 2 ms | 640 KB | Output isn't correct |
| 9 | Execution timed out | 1090 ms | 1536 KB | Time limit exceeded |
| 10 | Execution timed out | 1066 ms | 5248 KB | Time limit exceeded |
| 11 | Incorrect | 217 ms | 19816 KB | Output isn't correct |
| 12 | Incorrect | 96 ms | 19832 KB | Output isn't correct |
| 13 | Incorrect | 160 ms | 19576 KB | Output isn't correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 42 ms | 5756 KB | Output is correct |
| 2 | Execution timed out | 1093 ms | 28280 KB | Time limit exceeded |
| 3 | Correct | 105 ms | 29944 KB | Output is correct |
| 4 | Execution timed out | 1093 ms | 8952 KB | Time limit exceeded |
| 5 | Execution timed out | 1084 ms | 8960 KB | Time limit exceeded |
| 6 | Execution timed out | 1081 ms | 9084 KB | Time limit exceeded |
| 7 | Execution timed out | 1088 ms | 8576 KB | Time limit exceeded |
| 8 | Correct | 43 ms | 5752 KB | Output is correct |
| 9 | Execution timed out | 1101 ms | 27512 KB | Time limit exceeded |
| 10 | Execution timed out | 1064 ms | 28280 KB | Time limit exceeded |
| 11 | Execution timed out | 1078 ms | 28280 KB | Time limit exceeded |
| 12 | Execution timed out | 1091 ms | 27768 KB | Time limit exceeded |
| 13 | Correct | 99 ms | 23420 KB | Output is correct |
| 14 | Correct | 112 ms | 29944 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 107 ms | 14456 KB | Output isn't correct |
| 2 | Incorrect | 233 ms | 28664 KB | Output isn't correct |
| 3 | Correct | 129 ms | 21240 KB | Output is correct |
| 4 | Incorrect | 148 ms | 22520 KB | Output isn't correct |
| 5 | Incorrect | 149 ms | 23032 KB | Output isn't correct |
| 6 | Incorrect | 153 ms | 23112 KB | Output isn't correct |
| 7 | Incorrect | 154 ms | 22952 KB | Output isn't correct |
| 8 | Correct | 123 ms | 21368 KB | Output is correct |
| 9 | Incorrect | 238 ms | 27896 KB | Output isn't correct |
| 10 | Incorrect | 235 ms | 28792 KB | Output isn't correct |
| 11 | Incorrect | 232 ms | 28664 KB | Output isn't correct |
| 12 | Incorrect | 232 ms | 28664 KB | Output isn't correct |
| 13 | Correct | 201 ms | 26488 KB | Output is correct |
| 14 | Incorrect | 231 ms | 30072 KB | Output isn't correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Execution timed out | 1088 ms | 27512 KB | Time limit exceeded |
| 2 | Incorrect | 221 ms | 28536 KB | Output isn't correct |
| 3 | Correct | 103 ms | 26360 KB | Output is correct |
| 4 | Execution timed out | 1084 ms | 27512 KB | Time limit exceeded |
| 5 | Execution timed out | 1097 ms | 28408 KB | Time limit exceeded |
| 6 | Incorrect | 196 ms | 28408 KB | Output isn't correct |
| 7 | Incorrect | 226 ms | 28792 KB | Output isn't correct |
| 8 | Correct | 115 ms | 26360 KB | Output is correct |
| 9 | Correct | 123 ms | 30072 KB | Output is correct |