oj.uz

답안 #359332

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
359332 2021-01-26T19:44:06 Z Ahmad_Hasan Ball Machine (BOI13_ballmachine) C++17
100 / 100
 296 ms 28408 KB 
#include <bits/stdc++.h>
using namespace std;

int n;
vector<vector<int> >adj;
vector<vector<int> >prnt;
vector<int>mins;
int rot;
int l;
int dfs1(int cr=rot,int p=0){
    prnt[cr][0]=p;
    for(int i=1;i<=l;i++){
        prnt[cr][i]=prnt[prnt[cr][i-1]][i-1];
    }
    int mn=cr;
    for(int i=0;i<adj[cr].size();i++){
        mn=min(mn,dfs1(adj[cr][i],cr));
    }

    return mins[cr]=mn;
}

vector<int>order;

bool comp(int x,int y){
    return mins[x]<mins[y];
}

void dfs2(int cr=rot){
    int mn=cr;
    sort(adj[cr].begin(),adj[cr].end(),comp);
    for(int i=0;i<adj[cr].size();i++){
        dfs2(adj[cr][i]);
    }

    order.push_back(cr);
}

vector<int>vis;

pair<int,int> findpr(int x){
    int cnt=0;
    for(int i=l;i>=0;i--){
        if(vis[prnt[x][i]]){
            x=prnt[x][i];
            cnt+=(1<<i);
        }

    }

    return {x,cnt};
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);      cout.tie(0);
    int q;
    cin>>n>>q;
    adj=vector<vector<int> >(n+5);
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        if(x)
            adj[x].push_back(i);
        else
            rot=i;
    }
    vis=mins=vector<int>(n+5);
    l=log2(n)+1;
    prnt=vector<vector<int> >(n+5,vector<int>(l+5,0));
    dfs1();
    dfs2();

    priority_queue<pair<int,int> >pq;
    vector<int>num(n+5);
    for(int i=0;i<order.size();i++){
        pq.push({-i,order[i]});
        num[order[i]]=i;
    }
    /**for(int i=1;i<=n;i++){
        cout<<i<<':';
        for(int j=0;j<=l;j++){
            cout<<prnt[i][j]<<' ';
        }
        cout<<'\n';
    }*/
    while(q--){
        int t,x;
        cin>>t>>x;
        if(t==1){
            for(int i=0;i<x;i++){
                pair<int,int>p=pq.top();   pq.pop();
                p.first*=-1;
                if(i==x-1)
                    cout<<p.second<<'\n';
                vis[p.second]=1;
            }

        }else{

            pair<int,int> p=findpr(x);
            vis[p.first]=0;
            cout<<p.second<<'\n';
            pq.push({-num[p.first],p.first});
        }

    }


    return 0;
}
/**
7
2 4 6 1 3 5 7
6
3 6 4 5 1 2
*/

Compilation message

ballmachine.cpp: In function 'int dfs1(int, int)':
ballmachine.cpp:16:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for(int i=0;i<adj[cr].size();i++){
      |                 ~^~~~~~~~~~~~~~~
ballmachine.cpp: In function 'void dfs2(int)':
ballmachine.cpp:32:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int i=0;i<adj[cr].size();i++){
      |                 ~^~~~~~~~~~~~~~~
ballmachine.cpp:30:9: warning: unused variable 'mn' [-Wunused-variable]
   30 |     int mn=cr;
      |         ^~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:76:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(int i=0;i<order.size();i++){
      |                 ~^~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 121 ms 13672 KB Output is correct
3 Correct 79 ms 13672 KB Output is correct
4 Correct 1 ms 376 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 6 ms 1144 KB Output is correct
10 Correct 24 ms 3692 KB Output is correct
11 Correct 117 ms 13612 KB Output is correct
12 Correct 79 ms 13692 KB Output is correct
13 Correct 106 ms 13672 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 5992 KB Output is correct
2 Correct 211 ms 23524 KB Output is correct
3 Correct 98 ms 19580 KB Output is correct
4 Correct 63 ms 8040 KB Output is correct
5 Correct 73 ms 7932 KB Output is correct
6 Correct 62 ms 7912 KB Output is correct
7 Correct 65 ms 6888 KB Output is correct
8 Correct 38 ms 5992 KB Output is correct
9 Correct 183 ms 24056 KB Output is correct
10 Correct 215 ms 23652 KB Output is correct
11 Correct 196 ms 23816 KB Output is correct
12 Correct 201 ms 21484 KB Output is correct
13 Correct 163 ms 24804 KB Output is correct
14 Correct 99 ms 19432 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 90 ms 12264 KB Output is correct
2 Correct 232 ms 22272 KB Output is correct
3 Correct 188 ms 22496 KB Output is correct
4 Correct 150 ms 19180 KB Output is correct
5 Correct 156 ms 18916 KB Output is correct
6 Correct 158 ms 18872 KB Output is correct
7 Correct 149 ms 17632 KB Output is correct
8 Correct 190 ms 22496 KB Output is correct
9 Correct 218 ms 24300 KB Output is correct
10 Correct 238 ms 23788 KB Output is correct
11 Correct 240 ms 23848 KB Output is correct
12 Correct 238 ms 22252 KB Output is correct
13 Correct 296 ms 28408 KB Output is correct
14 Correct 136 ms 19808 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 226 ms 24300 KB Output is correct
2 Correct 232 ms 22124 KB Output is correct
3 Correct 194 ms 27876 KB Output is correct
4 Correct 235 ms 24300 KB Output is correct
5 Correct 258 ms 23788 KB Output is correct
6 Correct 210 ms 23708 KB Output is correct
7 Correct 228 ms 22124 KB Output is correct
8 Correct 188 ms 27876 KB Output is correct
9 Correct 98 ms 19460 KB Output is correct