oj.uz

답안 #42666

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
42666 2018-03-02T00:10:06 Z XmtosX Ball Machine (BOI13_ballmachine) C++14
100 / 100
 317 ms 38548 KB 
#include <bits/stdc++.h>
using namespace std;
int n,minn[100005],root,q,sprs[100005][30],cnt[100005],pro[100005],cur,b;
vector <int> v[100005];
set <pair<int,int > > s;
bool yes[100005];
void dfs (int x,int p)
{
    minn[x]=x;
    if (p!=-1)
        sprs[x][0]=p;
    for (int i=1;i<30;i++)
        sprs[x][i]=sprs[sprs[x][i-1]][i-1];
    for (int i=0;i<v[x].size();i++)
    {
        if (v[x][i]!=p)
        {
            dfs(v[x][i],x);
            minn[x]=min(minn[x],minn[v[x][i]]);
            cnt[x]++;
        }
    }
}
void build (int x,int p)
{
    set <pair<int,int> > s1;
    for (int i=0;i<v[x].size();i++)
    {
        if (v[x][i]!=p)
        {
            s1.insert({minn[v[x][i]],v[x][i]});
        }
    }
    while (!s1.empty())
    {
        build(s1.begin()->second,x);
        s1.erase(s1.begin());
    }
    pro[x]=++cur;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >>n>>q;
    for (int i=1;i<=n;i++)
    {
        int a;
        cin >>a;
        if (!a)
            root=i;
        else
        {
            v[a].push_back(i);
            v[i].push_back(a);
        }
    }
    dfs (root,-1);
    build (root,-1);
    for (int i=1;i<=n;i++)
    {
        if (!cnt[i])
        {
            s.insert({pro[i],i});
        }
    }
    while (q--)
    {
        int t,k;
        cin >>t>>k;
        if (t==1)
        {
            int x;
            while (k--)
            {
                x=s.begin()->second;
                s.erase(s.begin());
                yes[x]=true;
                if (x!=root)
                {
                    cnt[sprs[x][0]]--;
                    if (!cnt[sprs[x][0]])
                        s.insert({pro[sprs[x][0]],sprs[x][0]});
                }
            }
            cout <<x<<"\n";
        }
        else
        {
            int ans=0;
            for (int i=20;i>=0;i--)
            {
                if (yes[sprs[k][i]])
                {
                    k=sprs[k][i];
                    ans+= (1<<i);
                }
            }
            cout <<ans<<"\n";
            yes[k]=false;
            s.insert({pro[k],k});
            if (k!=root)
            {
                if (!cnt[sprs[k][0]])
                    s.erase({pro[sprs[k][0]],sprs[k][0]});
                cnt[sprs[k][0]]++;
            }
        }
    }
    return 0;
}

Compilation message

ballmachine.cpp: In function 'void dfs(int, int)':
ballmachine.cpp:14:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v[x].size();i++)
                   ^
ballmachine.cpp: In function 'void build(int, int)':
ballmachine.cpp:27:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v[x].size();i++)
                   ^
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:87:20: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
             cout <<x<<"\n";
                    ^

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2680 KB Output is correct
2 Correct 179 ms 15200 KB Output is correct
3 Correct 95 ms 15240 KB Output is correct
4 Correct 3 ms 15240 KB Output is correct
5 Correct 3 ms 15240 KB Output is correct
6 Correct 4 ms 15240 KB Output is correct
7 Correct 4 ms 15240 KB Output is correct
8 Correct 5 ms 15240 KB Output is correct
9 Correct 11 ms 15240 KB Output is correct
10 Correct 32 ms 15240 KB Output is correct
11 Correct 180 ms 15316 KB Output is correct
12 Correct 92 ms 15320 KB Output is correct
13 Correct 141 ms 15320 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 15320 KB Output is correct
2 Correct 250 ms 30260 KB Output is correct
3 Correct 133 ms 30260 KB Output is correct
4 Correct 85 ms 30260 KB Output is correct
5 Correct 101 ms 30260 KB Output is correct
6 Correct 82 ms 30260 KB Output is correct
7 Correct 88 ms 30260 KB Output is correct
8 Correct 47 ms 30260 KB Output is correct
9 Correct 226 ms 30260 KB Output is correct
10 Correct 268 ms 30492 KB Output is correct
11 Correct 213 ms 30492 KB Output is correct
12 Correct 226 ms 30492 KB Output is correct
13 Correct 166 ms 34076 KB Output is correct
14 Correct 144 ms 34076 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 113 ms 34076 KB Output is correct
2 Correct 294 ms 34076 KB Output is correct
3 Correct 179 ms 34076 KB Output is correct
4 Correct 162 ms 34076 KB Output is correct
5 Correct 186 ms 34076 KB Output is correct
6 Correct 196 ms 34076 KB Output is correct
7 Correct 172 ms 34076 KB Output is correct
8 Correct 179 ms 34076 KB Output is correct
9 Correct 255 ms 34076 KB Output is correct
10 Correct 300 ms 34076 KB Output is correct
11 Correct 283 ms 34076 KB Output is correct
12 Correct 317 ms 34076 KB Output is correct
13 Correct 285 ms 38548 KB Output is correct
14 Correct 252 ms 38548 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 250 ms 38548 KB Output is correct
2 Correct 267 ms 38548 KB Output is correct
3 Correct 198 ms 38548 KB Output is correct
4 Correct 258 ms 38548 KB Output is correct
5 Correct 296 ms 38548 KB Output is correct
6 Correct 233 ms 38548 KB Output is correct
7 Correct 269 ms 38548 KB Output is correct
8 Correct 186 ms 38548 KB Output is correct
9 Correct 140 ms 38548 KB Output is correct