Submission #1124063

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124063		Thanhs	Ball Machine (BOI13_ballmachine)	C++20	17.70 / 100	1098 ms	46564 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;

#define name "STEELWALL"
#define fi first
#define se second
#define int long long
#define endl '\n'
#define setmin(x, y) x = min((x), (y))
#define setmax(x, y) x = max((x), (y))
#define sqr(x) ((x) * (x))

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count());
int rand(int l, int r){return l + ((hdp() % (r - l + 1)) + r - l + 1) % (r - l + 1);}

const int NM = 1e5 + 5;
const int LG = 18;
const int inf = 1e9;

vector<int> g[NM];
int n, q, up[NM][LG], mn[2 * NM][LG + 1], a[NM], tin[NM], tout[NM], timer, d[NM], rt;

struct BIT
{
    int dt[NM];
    BIT(){memset(dt, 0, sizeof dt);}
    void upd(int x, int v)
    {
        for (; x <= n; x += x & -x)
            dt[x] += v;
    }
    void upd(int l, int r, int v)
    {
        upd(l, v);
        upd(r + 1, -v);
    }
    int get(int x)
    {
        int res = 0;
        for (; x; x -= x & -x)
            res += dt[x];
        return res;
    }
}bit;

struct ST
{
    pair<int, int> dt[4 * NM];
    void build(int x = 1, int l = 1, int r = n)
    {
        if (l == r)
        {
            dt[x] = make_pair(inf, l);
            return;
        }
        int m = l + r >> 1;
        build(x << 1, l, m);
        build(x << 1 | 1, m + 1, r);
        dt[x] = min(dt[x << 1], dt[x << 1 | 1]);
    }
    void upd(int i, int x = 1, int l = 1, int r = n)
    {
        if (l == r)
        {
            dt[x].fi = inf + a[i] - dt[x].fi;
            return;
        }
        int m = l + r >> 1;
        if (m >= i)
            upd(i, x << 1, l, m);
        else
            upd(i, x << 1 | 1, m + 1, r);
        dt[x] = min(dt[x << 1], dt[x << 1 | 1]);
    }
}st;

void dfs(int u)
{
    tin[u] = ++timer;
    mn[timer][0] = u;
    for (int v : g[u])
        dfs(v);
    tout[u] = timer;
}

int par(int u, int k)
{
    while (k)
    {
        u = up[u][__lg(k)];
        k ^= (1 << __lg(k));
    }
    return u;
}

void solve()
{
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        cin >> up[i][0];
        if (up[i][0])
            g[up[i][0]].push_back(i);
        else
            rt = i;
    }
    dfs(rt);
    for (int j = 1; (1 << j) <= n; j++)
        for (int i = 1; i <= n; i++)
            up[i][j] = up[up[i][j - 1]][j - 1];
    for (int j = 1; (1 << j) <= n; j++)
        for (int i = 1; i + (1 << j) - 1 <= timer; i++)
            mn[i][j] = min(mn[i][j - 1], mn[i + (1 << j - 1)][j - 1]);
    for (int i = 1; i <= n; i++)
    {
        int l = tin[i], r = tout[i];
        int L = __lg(r - l + 1);
        a[i] = min(mn[l][L], mn[r - (1 << L) + 1][L]);
    }
    st.build();
    for (int i = 1; i <= n; i++)
    {
        d[i] = g[i].size();
        if (!d[i])
            st.upd(i);
    }
    while (q--)
    {
        int op, t;
        cin >> op >> t;
        if (op == 1)
        {
            int u = 0;
            while (t--)
            {
                u = st.dt[1].se;
                st.upd(u);
                bit.upd(tin[u], tout[u], 1);
                d[up[u][0]]--;
                if (up[u][0] && !d[up[u][0]])
                    st.upd(up[u][0]);
            }
            cout << u << endl;
        }
        else
        {
            int x = bit.get(tin[t]);
            int u = par(t, x - 1);
            bit.upd(tin[u], tout[u], -1);
            d[up[u][0]]++;
            st.upd(u);
            cout << x - 1 << endl;
        }
    }
}

signed main()
{
    if (fopen("in.txt", "r")) 
    {
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    }
    else if (fopen(name".inp", "r"))
    {
        freopen(name".inp", "r", stdin);
        freopen(name".out", "w", stdout);
    }   
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int tc = 1; 
    // cin >> tc;
    while (tc--)
        solve();
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:169:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  169 |         freopen("in.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp:170:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  170 |         freopen("out.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp:174:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  174 |         freopen(name".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp:175:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  175 |         freopen(name".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 25
• Subtask 2: 8.5714 / 30
• Subtask 3: 8.5714 / 40
• Subtask 4: 0.5556 / 5