oj.uz

Submission #968343

# Submission time Handle Problem Language Result Execution time Memory
968343 2024-04-23T10:26:08 Z Mher777 Ball Machine (BOI13_ballmachine) C++17
16.1111 / 100
 400 ms 39688 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <iomanip>
#include <array>
#include <string>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <list>
#include <iterator>
#include <numeric>
#include <complex>
#include <utility>
#include <random>
#include <cassert>
#include <fstream>
using namespace std;
mt19937 rnd(7069);

/* -------------------- Typedefs -------------------- */

typedef int itn;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef float fl;
typedef long double ld;

/* -------------------- Usings -------------------- */

using vi = vector<int>;
using vll = vector<ll>;
using mii = map<int, int>;
using mll = map<ll, ll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

/* -------------------- Defines -------------------- */

#define ff first
#define ss second
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define mpr make_pair
#define yes cout<<"Yes\n"
#define no cout<<"No\n"
#define all(x) (x).begin(), (x).end()
#define USACO freopen("feast.in", "r", stdin); freopen("feast.out", "w", stdout);

/* -------------------- Constants -------------------- */

const int MAX = int(1e9 + 5);
const ll MAXL = ll(1e18) + 5ll;
const ll MOD = ll(1000000007);
const ll MOD2 = ll(998244353);

/* -------------------- Functions -------------------- */

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

void precision(int x) {
    cout.setf(ios::fixed | ios::showpoint);
    cout.precision(x);
}

ll gcd(ll a, ll b) {
    if (a == 0 || b == 0) return(max(a, b));
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}

ll range_sum(ll a, ll b) {
    if (a > b) return 0ll;
    ll dif = a - 1, cnt = b - a + 1;
    ll ans = ((b - a + 1) * (b - a + 2)) / 2;
    ans += ((b - a + 1) * dif);
    return ans;
}

string dec_to_bin(ll a) {
    string s = "";
    for (ll i = a; i > 0; ) {
        ll k = i % 2;
        i /= 2;
        char c = k + 48;
        s += c;
    }
    if (a == 0) {
        s = "0";
    }
    reverse(all(s));
    return s;
}

ll bin_to_dec(string s) {
    ll num = 0;
    for (int i = 0; i < s.size(); i++) {
        num *= 2ll;
        num += (s[i] - '0');
    }
    return num;
}

ll factorial_by_mod(ll n, ll mod) {
    ll ans = 1;
    ll num;
    for (ll i = 1; i <= n; ++i) {
        num = i % mod;
        ans *= num;
        ans %= mod;
    }
    return ans;
}

int isPrime(ll a) {
    if (a == 1) return 0;
    for (ll i = 2; i * i <= a; i++) {
        if (a % i == 0) return 0;
    }
    return 1;
}

ll binpow(ll a, ll b) {
    if (!a) return 0;
    ll ans = 1;
    while (b) {
        if (b & 1) {
            ans *= a;
        }
        b >>= 1;
        a *= a;
    }
    return ans;
}

ll binpow_by_mod(ll a, ll b, ll mod) {
    if (!a) return 0;
    ll ans = 1;
    while (b) {
        if (b & 1) {
            ans *= a;
            ans %= mod;
        }
        b >>= 1;
        a *= a;
        a %= mod;
    }
    return ans;
}

/* -------------------- Solution -------------------- */

const int N = 100005, M = 31;
int id[N], id_rev[N], p[N], up[N][M], dep[N], t[N * 4], lazy[N * 4], mark[N * 4], ran[N * 4];
vi g[N];
int n, q, lg, root, cur;

void prop(int pos) {
    if (!mark[pos]) return;
    t[2 * pos] = ran[2 * pos] * lazy[pos];
    t[2 * pos + 1] = ran[2 * pos + 1] * lazy[pos];
    lazy[2 * pos] = lazy[2 * pos + 1] = lazy[pos];
    mark[2 * pos] = mark[2 * pos + 1] = 1;
    mark[pos] = 0;
}

void bld(int l = 1, int r = n, int pos = 1) {
    ran[pos] = r - l + 1;
    if (l == r) return;
    int mid = (l + r) / 2;
    bld(l, mid, 2 * pos);
    bld(mid + 1, r, 2 * pos + 1);
}

int qry(int l, int r, int tl = 1, int tr = n, int pos = 1) {
    if (l == tl && r == tr) {
        return t[pos];
    }
    prop(pos);
    int mid = (tl + tr) / 2;
    if (mid >= r) {
        return qry(l, r, tl, mid, 2 * pos);
    }
    if (mid < l) {
        return qry(l, r, mid + 1, tr, 2 * pos + 1);
    }
    return qry(l, mid, tl, mid, 2 * pos) + qry(mid + 1, r, mid + 1, tr, 2 * pos + 1);
}

void upd(int l, int r, int val, int tl = 1, int tr = n, int pos = 1) {
    if (l == tl && r == tr) {
        t[pos] = val * ran[pos];
        lazy[pos] = val;
        mark[pos] = 1;
        return;
    }
    prop(pos);
    int mid = (tl + tr) / 2;
    if (mid >= r) {
        upd(l, r, val, tl, mid, 2 * pos);
    }
    else if (mid < l) {
        upd(l, r, val, mid + 1, tr, 2 * pos + 1);
    }
    else {
        upd(l, mid, val, tl, mid, 2 * pos);
        upd(mid + 1, r, val, mid + 1, tr, 2 * pos + 1);
    }
    t[pos] = t[2 * pos] + t[2 * pos + 1];
}

void dfs(int u = root, int depth = 0) {
    dep[u] = depth;
    up[u][0] = p[u];
    for (int i = 1; i <= lg; ++i) {
        up[u][i] = up[up[u][i - 1]][i - 1];
    }
    for (auto to : g[u]) {
        dfs(to, depth + 1);
    }
    id[u] = ++cur;
    id_rev[cur] = u;
}

int get_up(int u, int cnt) {
    for (int i = lg; i >= 0; --i) {
        if ((1 << i) <= cnt) {
            cnt -= (1 << i);
            u = up[u][i];
        }
    }
    return u;
}

void slv() {
    cin >> n >> q;
    lg = log2(n) + 1;
    for (int i = 1; i <= n; ++i) {
        cin >> p[i];
        if (!p[i]) root = p[i] = i;
        else g[p[i]].pub(i);
    }
    dfs();
    bld();
    while (q--) {
        int type, x;
        cin >> type >> x;
        if (type == 1) {
            int l = 1, r = n, mid, ind = 0;
            while (l <= r) {
                mid = (l + r) / 2;
                int cnt = qry(1, mid);
                if (mid - cnt < x) {
                    l = mid + 1;
                }
                else if (mid - cnt == x) {
                    ind = mid;
                    r = mid - 1;
                }
                else {
                    r = mid - 1;
                }
            }
            upd(1, ind, 1);
            cout << id_rev[ind] << '\n';
            continue;
        }
        int l = 1, r = dep[x], mid, ans = 0, gag = x;
        while (l <= r) {
            mid = (l + r) / 2;
            int u = get_up(x, mid);
            if (qry(id[u], id[u])) {
                gag = u;
                ans = mid;
                l = mid + 1;
            }
            else {
                r = mid - 1;
            }
        }
        upd(id[gag], id[gag], 0);
        cout << ans << '\n';
    }
}

void cs() {
    int tstc = 1;
    //cin >> tstc;
    while (tstc--) {
        slv();
    }
}

void precalc() {
    return;
}

int main() {
    fastio();
    precalc();
    //precision(0);
    cs();
    return 0;
}

Compilation message

ballmachine.cpp: In function 'll range_sum(ll, ll)':
ballmachine.cpp:95:21: warning: unused variable 'cnt' [-Wunused-variable]
   95 |     ll dif = a - 1, cnt = b - a + 1;
      |                     ^~~
ballmachine.cpp: In function 'll bin_to_dec(std::string)':
ballmachine.cpp:118:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |     for (int i = 0; i < s.size(); i++) {
      |                     ~~^~~~~~~~~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 8796 KB Output isn't correct
2 Runtime error 93 ms 39688 KB Execution killed with signal 11
3 Incorrect 82 ms 20560 KB Output isn't correct
4 Runtime error 15 ms 30044 KB Execution killed with signal 11
5 Incorrect 2 ms 8796 KB Output isn't correct
6 Incorrect 2 ms 8792 KB Output isn't correct
7 Runtime error 18 ms 30300 KB Execution killed with signal 11
8 Runtime error 15 ms 30300 KB Execution killed with signal 11
9 Incorrect 6 ms 9052 KB Output isn't correct
10 Runtime error 28 ms 31440 KB Execution killed with signal 11
11 Incorrect 99 ms 20480 KB Output isn't correct
12 Incorrect 76 ms 20568 KB Output isn't correct
13 Incorrect 80 ms 20308 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 13324 KB Output is correct
2 Incorrect 340 ms 27500 KB Output isn't correct
3 Incorrect 106 ms 23704 KB Output isn't correct
4 Runtime error 74 ms 34896 KB Execution killed with signal 11
5 Runtime error 34 ms 33876 KB Execution killed with signal 11
6 Incorrect 159 ms 15560 KB Output isn't correct
7 Incorrect 147 ms 13256 KB Output isn't correct
8 Correct 70 ms 13136 KB Output is correct
9 Incorrect 254 ms 27472 KB Output isn't correct
10 Incorrect 380 ms 27600 KB Output isn't correct
11 Incorrect 306 ms 26768 KB Output isn't correct
12 Incorrect 294 ms 25684 KB Output isn't correct
13 Correct 142 ms 28500 KB Output is correct
14 Incorrect 103 ms 23756 KB Output isn't correct

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 103 ms 19284 KB Output isn't correct
2 Incorrect 400 ms 26212 KB Output isn't correct
3 Correct 264 ms 27340 KB Output is correct
4 Incorrect 196 ms 25992 KB Output isn't correct
5 Incorrect 230 ms 25424 KB Output isn't correct
6 Incorrect 243 ms 25380 KB Output isn't correct
7 Incorrect 204 ms 24524 KB Output isn't correct
8 Correct 251 ms 27476 KB Output is correct
9 Incorrect 258 ms 27728 KB Output isn't correct
10 Incorrect 392 ms 27168 KB Output isn't correct
11 Incorrect 399 ms 27392 KB Output isn't correct
12 Incorrect 373 ms 26196 KB Output isn't correct
13 Correct 395 ms 30864 KB Output is correct
14 Incorrect 87 ms 24192 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 391 ms 27724 KB Output isn't correct
2 Incorrect 351 ms 25380 KB Output isn't correct
3 Correct 130 ms 30032 KB Output is correct
4 Incorrect 305 ms 27784 KB Output isn't correct
5 Incorrect 365 ms 27220 KB Output isn't correct
6 Incorrect 288 ms 26964 KB Output isn't correct
7 Incorrect 348 ms 25428 KB Output isn't correct
8 Correct 146 ms 30044 KB Output is correct
9 Incorrect 85 ms 23244 KB Output isn't correct