oj.uz

답안 #623575

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
623575 2022-08-06T02:04:14 Z Hanksburger Ball Machine (BOI13_ballmachine) C++17
100 / 100
 176 ms 23340 KB 
#include <bits/stdc++.h>
using namespace std;
int par[100005][17], mn[100005], t[100005], tt;
vector<int> child[100005];
set<pair<int, int> > s;
bool ball[100005];
bool cmp(int u, int v)
{
    return mn[u]<mn[v];
}
void dfs(int u)
{
    mn[u]=u;
    for (int v:child[u])
    {
        dfs(v);
        mn[u]=min(mn[u], mn[v]);
    }
}
void dfs2(int u)
{
    sort(child[u].begin(), child[u].end(), cmp);
    for (int v:child[u])
        dfs2(v);
    t[u]=++tt;
//    cout << "t[" << u << "]=" << t[u] << '\n';
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, q, r;
    cin >> n >> q;
    for (int i=1; i<=n; i++)
    {
        cin >> par[i][0];
        child[par[i][0]].push_back(i);
        if (!par[i][0])
            r=i;
    }
    for (int i=1; i<=16; i++)
        for (int j=1; j<=n; j++)
            par[j][i]=par[par[j][i-1]][i-1];
    dfs(r);
    dfs2(r);
    for (int i=1; i<=n; i++)
        s.insert({t[i], i});
    for (int i=1; i<=q; i++)
    {
        int x, y;
        cin >> x >> y;
        if (x==1)
        {
            for (int j=1; j<=y; j++)
            {
                int u=s.begin()->second;
                s.erase({t[u], u});
                ball[u]=1;
//                cout << "set ball[" << u << "] to 1\n";
                if (j==y)
                    cout << u << '\n';
            }
        }
        else
        {
            int cnt=0;
            for (int j=16; j>=0; j--)
            {
                if (ball[par[y][j]])
                {
                    y=par[y][j];
                    cnt+=1<<j;
                }
            }
            s.insert({t[y], y});
            ball[y]=0;
//            cout << "set ball[" << y << "] to 0\n";
            cout << cnt << '\n';
        }
    }
    return 0;
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:46:9: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   46 |     dfs2(r);
      |     ~~~~^~~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2684 KB Output is correct
2 Correct 100 ms 11996 KB Output is correct
3 Correct 62 ms 12184 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 3 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 7 ms 3284 KB Output is correct
10 Correct 19 ms 5028 KB Output is correct
11 Correct 101 ms 11980 KB Output is correct
12 Correct 60 ms 12108 KB Output is correct
13 Correct 88 ms 12080 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 6592 KB Output is correct
2 Correct 140 ms 19404 KB Output is correct
3 Correct 76 ms 16456 KB Output is correct
4 Correct 55 ms 7996 KB Output is correct
5 Correct 77 ms 7848 KB Output is correct
6 Correct 50 ms 7804 KB Output is correct
7 Correct 53 ms 7140 KB Output is correct
8 Correct 30 ms 6604 KB Output is correct
9 Correct 128 ms 19928 KB Output is correct
10 Correct 141 ms 19608 KB Output is correct
11 Correct 112 ms 19404 KB Output is correct
12 Correct 142 ms 17936 KB Output is correct
13 Correct 96 ms 20720 KB Output is correct
14 Correct 76 ms 16456 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 62 ms 11340 KB Output is correct
2 Correct 159 ms 18460 KB Output is correct
3 Correct 115 ms 19096 KB Output is correct
4 Correct 100 ms 16500 KB Output is correct
5 Correct 103 ms 16240 KB Output is correct
6 Correct 98 ms 16168 KB Output is correct
7 Correct 97 ms 15292 KB Output is correct
8 Correct 102 ms 19128 KB Output is correct
9 Correct 176 ms 20240 KB Output is correct
10 Correct 159 ms 19620 KB Output is correct
11 Correct 171 ms 19660 KB Output is correct
12 Correct 153 ms 18464 KB Output is correct
13 Correct 168 ms 23340 KB Output is correct
14 Correct 124 ms 16580 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 155 ms 20220 KB Output is correct
2 Correct 172 ms 18676 KB Output is correct
3 Correct 108 ms 23116 KB Output is correct
4 Correct 149 ms 20200 KB Output is correct
5 Correct 151 ms 19692 KB Output is correct
6 Correct 121 ms 19636 KB Output is correct
7 Correct 160 ms 18380 KB Output is correct
8 Correct 106 ms 23128 KB Output is correct
9 Correct 75 ms 16488 KB Output is correct