oj.uz

Submission #959474

# Submission time Handle Problem Language Result Execution time Memory
959474 2024-04-08T09:29:45 Z Neco_arc Ball Machine (BOI13_ballmachine) C++17
100 / 100
 166 ms 35592 KB 
#include <bits/stdc++.h>

#define ll long long
#define ull unsigned long long
#define all(x) x.begin(), x.end()
#define Neco "Ball Machine"
#define resp(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
#define getbit(x,i) ((x >> i)&1)
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define cntbit(x) __builtin_popcountll(x)
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define maxn (int) 2e5 + 7

using namespace std;

const ll mod = 1e9 + 7; //972663749
const ll base = 911382323;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ll GetRandom(ll l, ll r)
{
    return uniform_int_distribution<ll> (l, r)(rng);
}

int n, q, N, rt;
int cl[maxn], vt[maxn], cha[maxn][18];
int Min[maxn], h[maxn], a[maxn];
vector<int> edges[maxn];
set<int> S;

void pre_dfs(int u, int par) {
    for(int v : edges[u]) if(v != par) {
        pre_dfs(v, u);
        Min[u] = min(Min[u], Min[v]);
    }
}

int In[maxn], Out[maxn];
void dfs(int u, int par) {
    static int Time = 0;
    for(int v : edges[u]) if(v != par) {
        h[v] = h[u] + 1, cha[v][0] = u;
        fi(i, 1, 17) cha[v][i] = cha[cha[v][i - 1]][i - 1];
        dfs(v, u);
    }
    a[++N] = u, vt[u] = N;
}

int Add(int k, int ans = 0) {
    while(k--) {
        ans = a[*S.begin()];
        cl[a[*S.begin()]] = 1, S.erase(S.begin());
    }
    return ans;
}

int Del(int u, int ans = 0) {
    fid(i, 17, 0) if(cl[cha[u][i]]) u = cha[u][i], ans += (1 << i);
    S.insert(vt[u]), cl[u] = 0;
    return ans;
}

void solve()
{

    cin >> n >> q;

    int rt = 0;
    fi(i, 1, n) {
        Min[i] = i;
        int x; cin >> x;
        if(x == 0) rt = i;
        else edges[x].push_back(i);
    }

    pre_dfs(rt, 0);
    fi(i, 1, n) sort(all(edges[i]), [](int x, int y) { return Min[x] < Min[y]; } );
    dfs(rt, 0);

    fi(i, 1, n) S.insert(i);

    fi(i, 1, q) {
        int type, x;
        cin >> type >> x;
        if(type == 1) cout << Add(x) << '\n';
        else cout << Del(x) << '\n';
    }

}


int main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if(fopen(Neco".inp", "r")) {
        freopen(Neco".inp", "r", stdin);
        freopen(Neco".out", "w", stdout);
    }


    int nTest = 1;
//    cin >> nTest;


    while(nTest--)
    {
        solve();
    }


    return 0;
}

Compilation message

ballmachine.cpp: In function 'void dfs(int, int)':
ballmachine.cpp:43:16: warning: unused variable 'Time' [-Wunused-variable]
   43 |     static int Time = 0;
      |                ^~~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:103:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |         freopen(Neco".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp:104:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |         freopen(Neco".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp: At global scope:
ballmachine.cpp:43:16: warning: 'Time' defined but not used [-Wunused-variable]
   43 |     static int Time = 0;
      |                ^~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 72 ms 21332 KB Output is correct
3 Correct 58 ms 21332 KB Output is correct
4 Correct 3 ms 12632 KB Output is correct
5 Correct 2 ms 12632 KB Output is correct
6 Correct 3 ms 12636 KB Output is correct
7 Correct 3 ms 12636 KB Output is correct
8 Correct 3 ms 12788 KB Output is correct
9 Correct 6 ms 13144 KB Output is correct
10 Correct 15 ms 13688 KB Output is correct
11 Correct 69 ms 21588 KB Output is correct
12 Correct 47 ms 21352 KB Output is correct
13 Correct 70 ms 21352 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 15704 KB Output is correct
2 Correct 104 ms 30044 KB Output is correct
3 Correct 62 ms 25100 KB Output is correct
4 Correct 43 ms 18268 KB Output is correct
5 Correct 46 ms 18256 KB Output is correct
6 Correct 42 ms 18260 KB Output is correct
7 Correct 45 ms 17488 KB Output is correct
8 Correct 24 ms 15704 KB Output is correct
9 Correct 98 ms 30556 KB Output is correct
10 Correct 135 ms 30128 KB Output is correct
11 Correct 92 ms 30292 KB Output is correct
12 Correct 98 ms 27968 KB Output is correct
13 Correct 80 ms 33104 KB Output is correct
14 Correct 71 ms 25284 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 20572 KB Output is correct
2 Correct 117 ms 28240 KB Output is correct
3 Correct 97 ms 30120 KB Output is correct
4 Correct 85 ms 26448 KB Output is correct
5 Correct 74 ms 25904 KB Output is correct
6 Correct 81 ms 25784 KB Output is correct
7 Correct 81 ms 24368 KB Output is correct
8 Correct 82 ms 30292 KB Output is correct
9 Correct 119 ms 30544 KB Output is correct
10 Correct 134 ms 30324 KB Output is correct
11 Correct 114 ms 30544 KB Output is correct
12 Correct 125 ms 28240 KB Output is correct
13 Correct 166 ms 35592 KB Output is correct
14 Correct 99 ms 25516 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 30740 KB Output is correct
2 Correct 127 ms 28408 KB Output is correct
3 Correct 108 ms 35240 KB Output is correct
4 Correct 122 ms 30800 KB Output is correct
5 Correct 109 ms 30504 KB Output is correct
6 Correct 101 ms 30544 KB Output is correct
7 Correct 136 ms 28252 KB Output is correct
8 Correct 86 ms 35260 KB Output is correct
9 Correct 66 ms 25808 KB Output is correct