oj.uz

답안 #159677

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
159677 2019-10-23T21:30:42 Z Rouge_Hugo Ball Machine (BOI13_ballmachine) C++14
95.7143 / 100
 541 ms 33784 KB 
#include <bits/stdc++.h>

using namespace std;
set <pair<int,int>>s;
const int N=1e5+10;
vector<int>v1[N];
vector<pair<int,int>>v[N];
int n,q,lev[N],t[N],pa[N][25],yes[N];
void dfs (int x,int p)
{
    pa[x][0]=p;
    lev[x]=lev[p]+1;
    for(int i=1;i<22;i++)
    {
        pa[x][i]=pa[pa[x][i-1]][i-1];
    }
    for(auto it:v[x])
    {
        dfs(it.second,x);
    }
    t[x]=s.size();
    s.insert({t[x],x});
}
void add (int x)
{
    pair<int,int>last;
    while (x--)
    {
        last=*s.begin();
        yes[last.second]=1;
        s.erase(s.begin());
    }
    cout<<last.second<<endl;
}
void del(int x)
{
    int xx=x;
    for(int i=22;i>-1;i--)
    {
        if (yes[pa[xx][i]]==1)
            xx=pa[xx][i];
    }
    cout<<lev[x]-lev[xx]<<endl;
yes[xx]=0;
s.insert({t[xx],xx});
}
int dfs1 (int x,int p)
{
    int mn=x;
    for(auto it:v1[x])
    {
        mn=min(mn,dfs1(it,x));
    }
    v[p].push_back({mn,x});
    return mn;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int x;
    int root =1;
    cin>>n>>q;
    for(int i=1;i<n+1;i++)
    {
        cin>>x;
        if (x==0)
        {
            root=i;
            continue;
        }
        v1[x].push_back(i);
    }
    dfs1(root,0);
    for(int i=1;i<n;i++)
        sort(v[i].begin(),v[i].end());
    dfs (root,0);
    while (q--)
    {
        cin>>x;
        if (x==1)
        {
            cin>>x;
            add(x);

        }
        else {
            cin>>x;
            del(x);
        }
    }
}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 440 ms 17528 KB Output is correct
3 Correct 366 ms 17584 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 7 ms 5112 KB Output is correct
6 Correct 8 ms 5240 KB Output is correct
7 Correct 11 ms 5240 KB Output is correct
8 Correct 11 ms 5240 KB Output is correct
9 Correct 37 ms 5880 KB Output is correct
10 Correct 93 ms 8188 KB Output is correct
11 Correct 497 ms 17756 KB Output is correct
12 Correct 371 ms 17636 KB Output is correct
13 Correct 452 ms 17688 KB Output is correct

Subtask #2
25.7142857143 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 266 ms 10360 KB Output is correct
2 Correct 516 ms 28168 KB Output is correct
3 Correct 385 ms 23408 KB Output is correct
4 Correct 322 ms 12444 KB Output is correct
5 Incorrect 328 ms 12024 KB Output isn't correct
6 Incorrect 313 ms 11996 KB Output isn't correct
7 Correct 317 ms 11100 KB Output is correct
8 Correct 259 ms 10360 KB Output is correct
9 Correct 491 ms 29156 KB Output is correct
10 Correct 516 ms 28024 KB Output is correct
11 Correct 483 ms 28156 KB Output is correct
12 Correct 501 ms 26176 KB Output is correct
13 Correct 409 ms 30128 KB Output is correct
14 Correct 381 ms 23536 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 248 ms 16976 KB Output is correct
2 Correct 533 ms 26616 KB Output is correct
3 Correct 334 ms 27916 KB Output is correct
4 Correct 327 ms 24312 KB Output is correct
5 Correct 327 ms 23788 KB Output is correct
6 Correct 334 ms 23680 KB Output is correct
7 Correct 350 ms 22432 KB Output is correct
8 Correct 355 ms 27920 KB Output is correct
9 Correct 524 ms 29304 KB Output is correct
10 Correct 524 ms 28152 KB Output is correct
11 Correct 538 ms 28332 KB Output is correct
12 Correct 531 ms 26872 KB Output is correct
13 Correct 533 ms 33784 KB Output is correct
14 Correct 502 ms 24040 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 512 ms 29180 KB Output is correct
2 Correct 541 ms 26624 KB Output is correct
3 Correct 422 ms 33528 KB Output is correct
4 Correct 514 ms 29212 KB Output is correct
5 Correct 527 ms 28408 KB Output is correct
6 Correct 489 ms 28152 KB Output is correct
7 Correct 522 ms 26728 KB Output is correct
8 Correct 431 ms 33272 KB Output is correct
9 Correct 380 ms 23472 KB Output is correct