oj.uz

답안 #42665

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
42665 2018-03-02T00:06:05 Z XmtosX Ball Machine (BOI13_ballmachine) C++14
20.9524 / 100
 1000 ms 25612 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;
    b=n;
    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 (!cnt[i])
        {
            s.insert({pro[i],i});
        }
    }
    while (q--)
    {
        int t,k;
        cin >>t>>k;
        if (t==1)
        {
            int x;
            while (k--&&b)
            {
                x= s.begin()->second;
                s.erase(s.begin());
                b--;
                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;
            b++;
            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:88: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 1074 ms 2684 KB Time limit exceeded
2 Execution timed out 1076 ms 14688 KB Time limit exceeded
3 Incorrect 126 ms 15016 KB Output isn't correct
4 Execution timed out 1076 ms 15016 KB Time limit exceeded
5 Execution timed out 1070 ms 15016 KB Time limit exceeded
6 Incorrect 4 ms 15016 KB Output isn't correct
7 Execution timed out 1078 ms 15016 KB Time limit exceeded
8 Execution timed out 1083 ms 15016 KB Time limit exceeded
9 Execution timed out 1073 ms 15016 KB Time limit exceeded
10 Execution timed out 1070 ms 15016 KB Time limit exceeded
11 Execution timed out 1074 ms 15016 KB Time limit exceeded
12 Incorrect 81 ms 15172 KB Output isn't correct
13 Incorrect 123 ms 15244 KB Output isn't correct

Subtask #2
10.7142857143 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 15244 KB Output is correct
2 Execution timed out 1064 ms 23656 KB Time limit exceeded
3 Correct 113 ms 23656 KB Output is correct
4 Execution timed out 1087 ms 23656 KB Time limit exceeded
5 Execution timed out 1079 ms 23656 KB Time limit exceeded
6 Execution timed out 1063 ms 23656 KB Time limit exceeded
7 Execution timed out 1079 ms 23656 KB Time limit exceeded
8 Correct 49 ms 23656 KB Output is correct
9 Execution timed out 1077 ms 24108 KB Time limit exceeded
10 Execution timed out 1074 ms 24108 KB Time limit exceeded
11 Incorrect 190 ms 24108 KB Output isn't correct
12 Incorrect 201 ms 24108 KB Output isn't correct
13 Correct 134 ms 24108 KB Output is correct
14 Correct 114 ms 24108 KB Output is correct

Subtask #3
8.57142857143 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 97 ms 24108 KB Output isn't correct
2 Incorrect 238 ms 24108 KB Output isn't correct
3 Correct 156 ms 24108 KB Output is correct
4 Incorrect 141 ms 24108 KB Output isn't correct
5 Incorrect 176 ms 24108 KB Output isn't correct
6 Incorrect 165 ms 24108 KB Output isn't correct
7 Incorrect 160 ms 24108 KB Output isn't correct
8 Correct 145 ms 24108 KB Output is correct
9 Incorrect 252 ms 24108 KB Output isn't correct
10 Incorrect 251 ms 24112 KB Output isn't correct
11 Incorrect 232 ms 24200 KB Output isn't correct
12 Incorrect 231 ms 24200 KB Output isn't correct
13 Correct 244 ms 25612 KB Output is correct
14 Incorrect 224 ms 25612 KB Output isn't correct

Subtask #4
1.66666666667 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1063 ms 25612 KB Time limit exceeded
2 Incorrect 213 ms 25612 KB Output isn't correct
3 Correct 155 ms 25612 KB Output is correct
4 Execution timed out 1063 ms 25612 KB Time limit exceeded
5 Execution timed out 1082 ms 25612 KB Time limit exceeded
6 Incorrect 183 ms 25612 KB Output isn't correct
7 Incorrect 232 ms 25612 KB Output isn't correct
8 Correct 153 ms 25612 KB Output is correct
9 Correct 129 ms 25612 KB Output is correct