oj.uz

답안 #42660

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
42660 2018-03-01T23:46:28 Z XmtosX Ball Machine (BOI13_ballmachine) C++14
20.9524 / 100
 1000 ms 25644 KB 
#include <bits/stdc++.h>
using namespace std;
int n,minn[100005],root,q,sprs[100005][30],cnt[100005],pro[100005],cur;
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()
{
    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);
    for (int i=1;i<=n;i++)
    {
        if (v[i].size()==1&&i!=root)
        {
            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=29;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:83:20: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
             cout <<x<<"\n";
                    ^

Subtask #1
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1081 ms 2680 KB Time limit exceeded
2 Execution timed out 1064 ms 14696 KB Time limit exceeded
3 Incorrect 273 ms 15132 KB Output isn't correct
4 Execution timed out 1056 ms 15132 KB Time limit exceeded
5 Execution timed out 1080 ms 15132 KB Time limit exceeded
6 Incorrect 6 ms 15132 KB Output isn't correct
7 Execution timed out 1075 ms 15132 KB Time limit exceeded
8 Execution timed out 1076 ms 15132 KB Time limit exceeded
9 Execution timed out 1076 ms 15132 KB Time limit exceeded
10 Execution timed out 1084 ms 15132 KB Time limit exceeded
11 Execution timed out 1074 ms 15132 KB Time limit exceeded
12 Incorrect 305 ms 15284 KB Output isn't correct
13 Incorrect 327 ms 15284 KB Output isn't correct

Subtask #2
10.7142857143 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 180 ms 15284 KB Output is correct
2 Execution timed out 1089 ms 23724 KB Time limit exceeded
3 Correct 305 ms 23724 KB Output is correct
4 Execution timed out 1068 ms 23724 KB Time limit exceeded
5 Execution timed out 1078 ms 23724 KB Time limit exceeded
6 Execution timed out 1080 ms 23724 KB Time limit exceeded
7 Execution timed out 1065 ms 23724 KB Time limit exceeded
8 Correct 175 ms 23724 KB Output is correct
9 Execution timed out 1068 ms 24112 KB Time limit exceeded
10 Execution timed out 1075 ms 24112 KB Time limit exceeded
11 Incorrect 402 ms 24112 KB Output isn't correct
12 Incorrect 431 ms 24112 KB Output isn't correct
13 Correct 316 ms 24112 KB Output is correct
14 Correct 293 ms 24112 KB Output is correct

Subtask #3
8.57142857143 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 208 ms 24112 KB Output isn't correct
2 Incorrect 450 ms 24112 KB Output isn't correct
3 Correct 276 ms 24112 KB Output is correct
4 Incorrect 268 ms 24112 KB Output isn't correct
5 Incorrect 285 ms 24112 KB Output isn't correct
6 Incorrect 296 ms 24112 KB Output isn't correct
7 Incorrect 324 ms 24112 KB Output isn't correct
8 Correct 286 ms 24112 KB Output is correct
9 Incorrect 461 ms 24112 KB Output isn't correct
10 Incorrect 445 ms 24112 KB Output isn't correct
11 Incorrect 501 ms 24240 KB Output isn't correct
12 Incorrect 465 ms 24240 KB Output isn't correct
13 Correct 452 ms 25644 KB Output is correct
14 Incorrect 424 ms 25644 KB Output isn't correct

Subtask #4
1.66666666667 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1072 ms 25644 KB Time limit exceeded
2 Incorrect 474 ms 25644 KB Output isn't correct
3 Correct 354 ms 25644 KB Output is correct
4 Execution timed out 1066 ms 25644 KB Time limit exceeded
5 Execution timed out 1079 ms 25644 KB Time limit exceeded
6 Incorrect 395 ms 25644 KB Output isn't correct
7 Incorrect 429 ms 25644 KB Output isn't correct
8 Correct 397 ms 25644 KB Output is correct
9 Correct 311 ms 25644 KB Output is correct