oj.uz

Submission #1027064

# Submission time Handle Problem Language Result Execution time Memory
1027064 2024-07-18T20:08:50 Z hasan2006 Ball Machine (BOI13_ballmachine) C++17
0 / 100
 12 ms 10704 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 = 1e5 + 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

ballmachine.cpp: In function 'void solve()':
ballmachine.cpp:50:12: warning: unused variable 'q' [-Wunused-variable]
   50 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |            ^
ballmachine.cpp:50:20: warning: unused variable 'j' [-Wunused-variable]
   50 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                    ^
ballmachine.cpp:50:23: warning: unused variable 'l' [-Wunused-variable]
   50 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                       ^
ballmachine.cpp:50:26: warning: unused variable 'r' [-Wunused-variable]
   50 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                          ^
ballmachine.cpp:50:38: warning: unused variable 's' [-Wunused-variable]
   50 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                      ^
ballmachine.cpp:50:58: warning: unused variable 'mn' [-Wunused-variable]
   50 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                                          ^~
ballmachine.cpp:50:69: warning: unused variable 'mx' [-Wunused-variable]
   50 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                                                     ^~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:84:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp:85:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |         freopen("output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 10452 KB Execution killed with signal 11
2 Runtime error 7 ms 10448 KB Execution killed with signal 11
3 Runtime error 6 ms 10552 KB Execution killed with signal 11
4 Runtime error 7 ms 10448 KB Execution killed with signal 11
5 Runtime error 8 ms 10512 KB Execution killed with signal 11
6 Runtime error 7 ms 10532 KB Execution killed with signal 11
7 Runtime error 7 ms 10476 KB Execution killed with signal 11
8 Runtime error 6 ms 10452 KB Execution killed with signal 11
9 Runtime error 10 ms 10452 KB Execution killed with signal 11
10 Runtime error 7 ms 10452 KB Execution killed with signal 11
11 Runtime error 8 ms 10452 KB Execution killed with signal 11
12 Runtime error 6 ms 10416 KB Execution killed with signal 11
13 Runtime error 6 ms 10452 KB Execution killed with signal 11

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 10452 KB Execution killed with signal 11
2 Runtime error 7 ms 10556 KB Execution killed with signal 11
3 Runtime error 7 ms 10452 KB Execution killed with signal 11
4 Runtime error 7 ms 10528 KB Execution killed with signal 11
5 Runtime error 7 ms 10452 KB Execution killed with signal 11
6 Runtime error 9 ms 10448 KB Execution killed with signal 11
7 Runtime error 7 ms 10452 KB Execution killed with signal 11
8 Runtime error 6 ms 10452 KB Execution killed with signal 11
9 Runtime error 7 ms 10512 KB Execution killed with signal 11
10 Runtime error 7 ms 10452 KB Execution killed with signal 11
11 Runtime error 6 ms 10448 KB Execution killed with signal 11
12 Runtime error 8 ms 10628 KB Execution killed with signal 11
13 Runtime error 7 ms 10452 KB Execution killed with signal 11
14 Runtime error 7 ms 10452 KB Execution killed with signal 11

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 10452 KB Execution killed with signal 11
2 Runtime error 7 ms 10448 KB Execution killed with signal 11
3 Runtime error 7 ms 10452 KB Execution killed with signal 11
4 Runtime error 7 ms 10628 KB Execution killed with signal 11
5 Runtime error 6 ms 10452 KB Execution killed with signal 11
6 Runtime error 6 ms 10452 KB Execution killed with signal 11
7 Runtime error 6 ms 10452 KB Execution killed with signal 11
8 Runtime error 7 ms 10404 KB Execution killed with signal 11
9 Runtime error 7 ms 10452 KB Execution killed with signal 11
10 Runtime error 7 ms 10704 KB Execution killed with signal 11
11 Runtime error 6 ms 10452 KB Execution killed with signal 11
12 Runtime error 9 ms 10452 KB Execution killed with signal 11
13 Runtime error 7 ms 10452 KB Execution killed with signal 11
14 Runtime error 8 ms 10464 KB Execution killed with signal 11

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 10448 KB Execution killed with signal 11
2 Runtime error 7 ms 10452 KB Execution killed with signal 11
3 Runtime error 8 ms 10452 KB Execution killed with signal 11
4 Runtime error 7 ms 10452 KB Execution killed with signal 11
5 Runtime error 7 ms 10452 KB Execution killed with signal 11
6 Runtime error 12 ms 10452 KB Execution killed with signal 11
7 Runtime error 7 ms 10440 KB Execution killed with signal 11
8 Runtime error 7 ms 10448 KB Execution killed with signal 11
9 Runtime error 7 ms 10452 KB Execution killed with signal 11