oj.uz

답안 #42664

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
42664 2018-03-01T23:59:19 Z XmtosX Ball Machine (BOI13_ballmachine) C++14
20.9524 / 100
 1000 ms 25532 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()
{
    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);
    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]});
                }
                else
                    break;
            }
            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: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 1085 ms 2680 KB Time limit exceeded
2 Execution timed out 1082 ms 14948 KB Time limit exceeded
3 Incorrect 84 ms 15016 KB Output isn't correct
4 Execution timed out 1085 ms 15016 KB Time limit exceeded
5 Execution timed out 1062 ms 15016 KB Time limit exceeded
6 Incorrect 4 ms 15016 KB Output isn't correct
7 Execution timed out 1062 ms 15016 KB Time limit exceeded
8 Execution timed out 1061 ms 15016 KB Time limit exceeded
9 Execution timed out 1064 ms 15016 KB Time limit exceeded
10 Execution timed out 1066 ms 15016 KB Time limit exceeded
11 Execution timed out 1069 ms 15016 KB Time limit exceeded
12 Incorrect 86 ms 15200 KB Output isn't correct
13 Incorrect 123 ms 15200 KB Output isn't correct

Subtask #2
10.7142857143 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 15200 KB Output is correct
2 Execution timed out 1074 ms 23656 KB Time limit exceeded
3 Correct 110 ms 23656 KB Output is correct
4 Execution timed out 1064 ms 23656 KB Time limit exceeded
5 Execution timed out 1071 ms 23656 KB Time limit exceeded
6 Execution timed out 1087 ms 23656 KB Time limit exceeded
7 Execution timed out 1083 ms 23656 KB Time limit exceeded
8 Correct 42 ms 23656 KB Output is correct
9 Execution timed out 1085 ms 23980 KB Time limit exceeded
10 Execution timed out 1056 ms 23980 KB Time limit exceeded
11 Incorrect 183 ms 23980 KB Output isn't correct
12 Incorrect 210 ms 23980 KB Output isn't correct
13 Correct 153 ms 23980 KB Output is correct
14 Correct 104 ms 23980 KB Output is correct

Subtask #3
8.57142857143 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 95 ms 23980 KB Output isn't correct
2 Incorrect 226 ms 23980 KB Output isn't correct
3 Correct 147 ms 23980 KB Output is correct
4 Incorrect 149 ms 23980 KB Output isn't correct
5 Incorrect 152 ms 23980 KB Output isn't correct
6 Incorrect 150 ms 23980 KB Output isn't correct
7 Incorrect 145 ms 23980 KB Output isn't correct
8 Correct 140 ms 23980 KB Output is correct
9 Incorrect 225 ms 23980 KB Output isn't correct
10 Incorrect 259 ms 24040 KB Output isn't correct
11 Incorrect 242 ms 24040 KB Output isn't correct
12 Incorrect 260 ms 24040 KB Output isn't correct
13 Correct 220 ms 25532 KB Output is correct
14 Incorrect 245 ms 25532 KB Output isn't correct

Subtask #4
1.66666666667 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1064 ms 25532 KB Time limit exceeded
2 Incorrect 233 ms 25532 KB Output isn't correct
3 Correct 159 ms 25532 KB Output is correct
4 Execution timed out 1059 ms 25532 KB Time limit exceeded
5 Execution timed out 1080 ms 25532 KB Time limit exceeded
6 Incorrect 194 ms 25532 KB Output isn't correct
7 Incorrect 221 ms 25532 KB Output isn't correct
8 Correct 153 ms 25532 KB Output is correct
9 Correct 131 ms 25532 KB Output is correct