oj.uz

답안 #869671

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
869671 2023-11-05T08:53:43 Z 12345678 Ball Machine (BOI13_ballmachine) C++17
100 / 100
 279 ms 32848 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5, kx=17;
int n, q, x, pa[nx][kx], mn[nx], t, id[nx], rid[nx], c, lvl[nx], rt;
vector<int> d[nx];

struct segtree
{
    int d[4*nx], lz[4*nx];
    void pushlz(int l, int r, int i)
    {
        if (!lz[i]) return;
        lz[i]=0;
        d[i]=r-l+1;
        if (l==r) return;
        lz[2*i]=lz[2*i+1]=1;
    }
    void update(int l, int r, int i, int ql, int qr)
    {
        pushlz(l, r, i);
        if (qr<l||r<ql) return;
        if (ql<=l&&r<=qr) return lz[i]=1, pushlz(l, r, i), void();
        int md=(l+r)/2;
        update(l, md, 2*i, ql, qr);
        update(md+1, r, 2*i+1, ql, qr);
        d[i]=d[2*i]+d[2*i+1];
    }
    void update2(int l, int r, int i, int idx)
    {
        pushlz(l, r, i);
        if (r<idx||idx<l) return;
        if (l==r) return void(d[i]=0);
        int md=(l+r)/2;
        update2(l, md, 2*i, idx);
        update2(md+1, r, 2*i+1, idx);
        d[i]=d[2*i]+d[2*i+1];
    }
    int query(int l, int r, int i, int key)
    {
        pushlz(l, r, i);
        if (l==r) return l;
        int md=(l+r)/2;
        if (md-l+1-d[2*i]>=key) return query(l, md, 2*i, key);
        else return query(md+1, r, 2*i+1, key-(md-l+1-d[2*i]));
    }
    bool query2(int l, int r, int i, int idx)
    {
        pushlz(l, r, i);
        if (idx<l||r<idx) return 0;
        if (l==r) return d[i]==1;
        int md=(l+r)/2;
        return query2(l, md, 2*i, idx)||query2(md+1, r, 2*i+1, idx);
    }
} s;

void dfs(int u, int p)
{
    pa[u][0]=p; lvl[u]=lvl[p]+1;
    mn[u]=u;
    for (int i=1; i<kx; i++) pa[u][i]=pa[pa[u][i-1]][i-1];
    for (auto v:d[u]) dfs(v, u), mn[u]=min(mn[u], mn[v]);
}

void dfs2(int u)
{
    vector<pair<int, int>> tmp;
    for (auto v:d[u]) tmp.push_back({mn[v], v});
    sort(tmp.begin(), tmp.end());
    for (auto [x, y]:tmp) dfs2(y);
    id[u]=++t;
    rid[t]=u;
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>q;
    for (int i=1; i<=n; i++) 
    {
        cin>>x;
        if (x!=0) d[x].push_back(i);
        else rt=i;
    }
    dfs(rt, rt); dfs2(rt);
    while (q--)
    {
        cin>>t>>x;
        if (t==1) 
        {
            x=s.query(1, n, 1, x);
            s.update(1, n, 1, 1, x);
            cout<<rid[x]<<'\n';
        }
        else
        {
            int sv=x;
            for (int i=kx-1; i>=0; i--) if (s.query2(1, n, 1, id[pa[x][i]])==1) x=pa[x][i];
            s.update2(1, n, 1, id[x]);
            cout<<lvl[sv]-lvl[x]<<'\n';
        }
    }
}

/*
8 9
0
1
2
2
3
3
4
6
1 8
2 5
2 7
2 8
1 3
2 8
2 8
2 8
2 8
*/

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 164 ms 12648 KB Output is correct
3 Correct 83 ms 12112 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 10 ms 6748 KB Output is correct
10 Correct 28 ms 7004 KB Output is correct
11 Correct 158 ms 12940 KB Output is correct
12 Correct 85 ms 12116 KB Output is correct
13 Correct 141 ms 11864 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 10320 KB Output is correct
2 Correct 251 ms 23168 KB Output is correct
3 Correct 91 ms 14036 KB Output is correct
4 Correct 124 ms 12212 KB Output is correct
5 Correct 160 ms 12356 KB Output is correct
6 Correct 148 ms 11780 KB Output is correct
7 Correct 142 ms 10588 KB Output is correct
8 Correct 65 ms 10120 KB Output is correct
9 Correct 229 ms 23472 KB Output is correct
10 Correct 252 ms 23116 KB Output is correct
11 Correct 222 ms 22096 KB Output is correct
12 Correct 234 ms 18528 KB Output is correct
13 Correct 119 ms 27988 KB Output is correct
14 Correct 93 ms 14036 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 105 ms 15132 KB Output is correct
2 Correct 258 ms 19856 KB Output is correct
3 Correct 161 ms 27140 KB Output is correct
4 Correct 138 ms 20296 KB Output is correct
5 Correct 160 ms 20004 KB Output is correct
6 Correct 162 ms 20180 KB Output is correct
7 Correct 159 ms 16976 KB Output is correct
8 Correct 176 ms 27296 KB Output is correct
9 Correct 215 ms 24136 KB Output is correct
10 Correct 268 ms 23708 KB Output is correct
11 Correct 267 ms 23636 KB Output is correct
12 Correct 251 ms 19788 KB Output is correct
13 Correct 267 ms 32848 KB Output is correct
14 Correct 151 ms 15436 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 241 ms 23936 KB Output is correct
2 Correct 257 ms 19480 KB Output is correct
3 Correct 131 ms 31072 KB Output is correct
4 Correct 247 ms 23636 KB Output is correct
5 Correct 279 ms 23120 KB Output is correct
6 Correct 233 ms 22096 KB Output is correct
7 Correct 250 ms 19280 KB Output is correct
8 Correct 134 ms 31060 KB Output is correct
9 Correct 91 ms 14028 KB Output is correct