oj.uz

답안 #300769

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
300769 2020-09-17T13:20:13 Z vipghn2003 Ball Machine (BOI13_ballmachine) C++14
100 / 100
 282 ms 32380 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
using namespace std;

const int N=1e5+5;
int n,q,mn[N],pos[N],cnt,col[N],p[N][20];
vector<int>adj[N];

void dfs(int u,int par=-1)
{
    for(int i=1;i<=18;i++) p[u][i]=p[p[u][i-1]][i-1];
    mn[u]=u;
    for(auto&v:adj[u])
    {
        if(v==par) continue;
        p[v][0]=u;
        dfs(v,u);
        mn[u]=min(mn[u],mn[v]);
    }
}

void go(int u,int par=-1)
{
    vector<pii>order;
    for(auto&v:adj[u]) if(v!=par) order.push_back(mp(mn[v],v));
    sort(order.begin(),order.end());
    for(auto&v:order) go(v.se,u);
    pos[u]=++cnt;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>q;
    int root;
    for(int i=1;i<=n;i++)
    {
        int p;
        cin>>p;
        if(!p) root=i;
        else adj[p].push_back(i);
    }
    dfs(root);
    go(root);
    set<pii>empty_node;
    for(int i=1;i<=n;i++) empty_node.insert(mp(pos[i],i));
    while(q--)
    {
        int type,x;
        cin>>type>>x;
        int res=0;
        if(type==1)
        {
            while(x--)
            {
                auto it=empty_node.begin();
                res=(*it).se;
                col[res]=1;
                empty_node.erase(it);
            }
            cout<<res<<'\n';
            continue;
        }
        for(int i=18;i>=0;i--)
        {
            if(col[p[x][i]]==1)
            {
                res+=(1<<i);
                x=p[x][i];
            }
        }
        empty_node.insert(mp(pos[x],x));
        col[x]=0;
        cout<<res<<'\n';
    }
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:48:7: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   48 |     go(root);
      |     ~~^~~~~~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 154 ms 14004 KB Output is correct
3 Correct 95 ms 13944 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 3 ms 2816 KB Output is correct
7 Correct 4 ms 2816 KB Output is correct
8 Correct 3 ms 2816 KB Output is correct
9 Correct 10 ms 3456 KB Output is correct
10 Correct 26 ms 5504 KB Output is correct
11 Correct 161 ms 14200 KB Output is correct
12 Correct 94 ms 13816 KB Output is correct
13 Correct 127 ms 14200 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 8572 KB Output is correct
2 Correct 244 ms 25568 KB Output is correct
3 Correct 110 ms 18536 KB Output is correct
4 Correct 79 ms 10144 KB Output is correct
5 Correct 82 ms 9976 KB Output is correct
6 Correct 73 ms 9976 KB Output is correct
7 Correct 77 ms 8696 KB Output is correct
8 Correct 44 ms 8696 KB Output is correct
9 Correct 215 ms 25848 KB Output is correct
10 Correct 236 ms 25592 KB Output is correct
11 Correct 200 ms 25464 KB Output is correct
12 Correct 226 ms 22520 KB Output is correct
13 Correct 170 ms 28408 KB Output is correct
14 Correct 113 ms 18536 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 103 ms 14308 KB Output is correct
2 Correct 273 ms 22776 KB Output is correct
3 Correct 180 ms 26232 KB Output is correct
4 Correct 173 ms 21140 KB Output is correct
5 Correct 181 ms 20860 KB Output is correct
6 Correct 179 ms 20856 KB Output is correct
7 Correct 177 ms 18680 KB Output is correct
8 Correct 196 ms 26160 KB Output is correct
9 Correct 261 ms 26104 KB Output is correct
10 Correct 275 ms 25848 KB Output is correct
11 Correct 282 ms 25744 KB Output is correct
12 Correct 277 ms 22904 KB Output is correct
13 Correct 281 ms 32380 KB Output is correct
14 Correct 199 ms 19432 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 256 ms 26212 KB Output is correct
2 Correct 261 ms 22776 KB Output is correct
3 Correct 191 ms 31608 KB Output is correct
4 Correct 247 ms 26072 KB Output is correct
5 Correct 267 ms 25720 KB Output is correct
6 Correct 210 ms 25592 KB Output is correct
7 Correct 256 ms 22776 KB Output is correct
8 Correct 189 ms 31608 KB Output is correct
9 Correct 110 ms 18532 KB Output is correct