| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1027063 | 2024-07-18T20:07:55 Z | hasan2006 | Ball Machine (BOI13_ballmachine) | C++17 | 1000 ms | 58376 KB |
#include <bits/stdc++.h>
using namespace std;
#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define se second
#define fi first
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"
const int N = 5e5 + 9 , mod = 1e9 + 7;
ll a[N] , b[N] , dp[N] , c[N] , d[N] , p[N][22] , timer = 0;
vector<int>v[N];
void dfs(int n){
d[n] = a[n];
for(auto to : v[n])
dfs(to);
d[p[n][0]] = min(d[p[n][0]] , d[n]);
}
set<pair<int,int>>st , ss;
void dfs1(int n){
dp[n] = dp[p[n][0]] + 1;
vector<pair<int,int>>vc;
for(int i =1; i <= 20; i++)
p[n][i] = p[p[n][i - 1]][i - 1];
for(auto to : v[n])
vc.pb({d[to] , to});
sort(all(vc));
for(auto to : vc)
dfs1(to.se);
c[n] = ++timer;
st.insert({c[n] , n});
}
void solve()
{
ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
cin>>n>>m;
for(i = 1; i <= n; i++){
cin>>p[i][0];
v[p[i][0]].pb(i);
if(p[i][0] == 0)
x = i;
}
dfs(x);
dfs1(x);
while(m--){
cin>>k>>x;
if(k == 1){
while(x--){
y = st.begin()->se;
st.erase(st.begin());
}
cout<<y<<"\n";
}else{
f = x;
for(i = 20; i >= 0; i--)
if(p[x][i] && st.find({c[p[x][i]] , p[x][i]}) == st.end())
x = p[x][i];
cout<<dp[f] - dp[x]<<"\n";
st.insert({c[x] , x});
}
}
}
int main(){
TL;
/*#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif*/
int t = 1;
// cin>>t;
while(t--)
{
solve();
}
}
// Author : حسن
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 3 ms | 16988 KB | Output isn't correct |
| 2 | Execution timed out | 1101 ms | 35160 KB | Time limit exceeded |
| 3 | Incorrect | 50 ms | 35156 KB | Output isn't correct |
| 4 | Execution timed out | 1076 ms | 16988 KB | Time limit exceeded |
| 5 | Incorrect | 3 ms | 16988 KB | Output isn't correct |
| 6 | Incorrect | 3 ms | 16988 KB | Output isn't correct |
| 7 | Execution timed out | 1096 ms | 16988 KB | Time limit exceeded |
| 8 | Execution timed out | 1055 ms | 16988 KB | Time limit exceeded |
| 9 | Incorrect | 8 ms | 17244 KB | Output isn't correct |
| 10 | Execution timed out | 1094 ms | 22532 KB | Time limit exceeded |
| 11 | Incorrect | 101 ms | 35156 KB | Output isn't correct |
| 12 | Incorrect | 55 ms | 35252 KB | Output isn't correct |
| 13 | Incorrect | 78 ms | 35132 KB | Output isn't correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 36 ms | 25712 KB | Output is correct |
| 2 | Incorrect | 235 ms | 51064 KB | Output isn't correct |
| 3 | Incorrect | 59 ms | 43620 KB | Output isn't correct |
| 4 | Execution timed out | 1061 ms | 28112 KB | Time limit exceeded |
| 5 | Execution timed out | 1060 ms | 27740 KB | Time limit exceeded |
| 6 | Incorrect | 130 ms | 28196 KB | Output isn't correct |
| 7 | Incorrect | 107 ms | 24880 KB | Output isn't correct |
| 8 | Correct | 34 ms | 25684 KB | Output is correct |
| 9 | Incorrect | 165 ms | 51028 KB | Output isn't correct |
| 10 | Incorrect | 225 ms | 51028 KB | Output isn't correct |
| 11 | Incorrect | 184 ms | 50936 KB | Output isn't correct |
| 12 | Incorrect | 213 ms | 45664 KB | Output isn't correct |
| 13 | Correct | 92 ms | 53588 KB | Output is correct |
| 14 | Incorrect | 59 ms | 43588 KB | Output isn't correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 74 ms | 32992 KB | Output isn't correct |
| 2 | Incorrect | 258 ms | 47948 KB | Output isn't correct |
| 3 | Correct | 146 ms | 49492 KB | Output is correct |
| 4 | Incorrect | 114 ms | 43720 KB | Output isn't correct |
| 5 | Incorrect | 167 ms | 43528 KB | Output isn't correct |
| 6 | Incorrect | 174 ms | 43704 KB | Output isn't correct |
| 7 | Incorrect | 171 ms | 41044 KB | Output isn't correct |
| 8 | Correct | 148 ms | 49552 KB | Output is correct |
| 9 | Incorrect | 172 ms | 51540 KB | Output isn't correct |
| 10 | Incorrect | 246 ms | 51028 KB | Output isn't correct |
| 11 | Incorrect | 251 ms | 51152 KB | Output isn't correct |
| 12 | Incorrect | 260 ms | 48012 KB | Output isn't correct |
| 13 | Correct | 235 ms | 58376 KB | Output is correct |
| 14 | Incorrect | 88 ms | 43844 KB | Output isn't correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 211 ms | 51216 KB | Output isn't correct |
| 2 | Incorrect | 253 ms | 47956 KB | Output isn't correct |
| 3 | Correct | 99 ms | 58196 KB | Output is correct |
| 4 | Incorrect | 213 ms | 51284 KB | Output isn't correct |
| 5 | Incorrect | 270 ms | 51028 KB | Output isn't correct |
| 6 | Incorrect | 230 ms | 51044 KB | Output isn't correct |
| 7 | Incorrect | 260 ms | 47956 KB | Output isn't correct |
| 8 | Correct | 98 ms | 58196 KB | Output is correct |
| 9 | Incorrect | 56 ms | 43488 KB | Output isn't correct |