oj.uz

답안 #713146

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
713146 2023-03-21T08:43:07 Z JJAnawat Ball Machine (BOI13_ballmachine) C++17
100 / 100
 360 ms 25220 KB 
#include<bits/stdc++.h>

using namespace std;

int pa[100005][18];
vector<int> g[100005];
int mn[100005];
int tout[100005],ord[100005],counter=0;
set<int> s;

void dfs1(int u){
    mn[u]=u;
    for(auto v:g[u]){
        dfs1(v);
        mn[u]=min(mn[u],mn[v]);
    }
}

void dfs2(int u){
    for(auto v:g[u])
        dfs2(v);
    tout[u]=++counter;
    ord[counter]=u;
}

main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n,q;
    cin >> n >> q;
    int rt=0;
    for(int i=1,x;i<=n;i++){
        cin >> x;
        pa[i][0]=x;
        if(!x)
            rt=i;
        else
            g[x].push_back(i);
    }
    dfs1(rt);
    for(int i=1;i<=n;i++){
        sort(g[i].begin(),g[i].end(),[&](int x,int y){
            return mn[x]<mn[y];
        });
    }
    for(int j=1;j<18;j++)
        for(int i=1;i<=n;i++)
            pa[i][j]=pa[pa[i][j-1]][j-1];
    dfs2(rt);
    for(int i=1;i<=n;i++)
        s.insert(i);
    int t,x,ans;
    while(q--){
        cin >> t >> x;
        if(t==1){
            ans=0;
            while(x--){
                ans=*s.begin();
                s.erase(s.begin());
            }
            cout << ord[ans] << "\n";
        }
        else{
            ans=0;
            for(int i=17;i>=0;i--){
                int px=pa[x][i];
                if(px!=0&&s.find(tout[px])==s.end()){
                    ans+=(1<<i);
                    x=px;
                }
            }
            s.insert(tout[x]);
            cout << ans << "\n";
        }
    }
}

Compilation message

ballmachine.cpp:26:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   26 | main(){
      | ^~~~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 124 ms 13428 KB Output is correct
3 Correct 60 ms 13428 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2680 KB Output is correct
6 Correct 3 ms 2772 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 3 ms 2772 KB Output is correct
9 Correct 8 ms 3332 KB Output is correct
10 Correct 24 ms 5316 KB Output is correct
11 Correct 128 ms 13456 KB Output is correct
12 Correct 68 ms 13516 KB Output is correct
13 Correct 96 ms 13460 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 7244 KB Output is correct
2 Correct 347 ms 21384 KB Output is correct
3 Correct 84 ms 18032 KB Output is correct
4 Correct 94 ms 8848 KB Output is correct
5 Correct 187 ms 8724 KB Output is correct
6 Correct 132 ms 8652 KB Output is correct
7 Correct 125 ms 7952 KB Output is correct
8 Correct 48 ms 7172 KB Output is correct
9 Correct 231 ms 21816 KB Output is correct
10 Correct 281 ms 21392 KB Output is correct
11 Correct 282 ms 21448 KB Output is correct
12 Correct 253 ms 19836 KB Output is correct
13 Correct 135 ms 22392 KB Output is correct
14 Correct 104 ms 17992 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 12268 KB Output is correct
2 Correct 324 ms 20340 KB Output is correct
3 Correct 199 ms 20472 KB Output is correct
4 Correct 137 ms 18068 KB Output is correct
5 Correct 189 ms 17576 KB Output is correct
6 Correct 172 ms 17468 KB Output is correct
7 Correct 184 ms 16740 KB Output is correct
8 Correct 203 ms 20452 KB Output is correct
9 Correct 221 ms 21964 KB Output is correct
10 Correct 313 ms 21556 KB Output is correct
11 Correct 314 ms 21588 KB Output is correct
12 Correct 343 ms 20440 KB Output is correct
13 Correct 360 ms 25220 KB Output is correct
14 Correct 142 ms 18508 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 255 ms 22104 KB Output is correct
2 Correct 297 ms 20364 KB Output is correct
3 Correct 147 ms 24944 KB Output is correct
4 Correct 246 ms 22140 KB Output is correct
5 Correct 328 ms 21580 KB Output is correct
6 Correct 317 ms 21516 KB Output is correct
7 Correct 304 ms 20356 KB Output is correct
8 Correct 159 ms 24900 KB Output is correct
9 Correct 91 ms 18040 KB Output is correct