oj.uz

Submission #42662

# Submission time Handle Problem Language Result Execution time Memory
42662 2018-03-01T23:57:11 Z XmtosX Ball Machine (BOI13_ballmachine) C++14
20.9524 / 100
 1000 ms 25576 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]});
                }
            }
            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:86:20: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
             cout <<x<<"\n";
                    ^

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1080 ms 2680 KB Time limit exceeded
2 Execution timed out 1089 ms 14688 KB Time limit exceeded
3 Incorrect 97 ms 15144 KB Output isn't correct
4 Execution timed out 1066 ms 15144 KB Time limit exceeded
5 Execution timed out 1083 ms 15144 KB Time limit exceeded
6 Incorrect 4 ms 15144 KB Output isn't correct
7 Execution timed out 1079 ms 15144 KB Time limit exceeded
8 Execution timed out 1060 ms 15144 KB Time limit exceeded
9 Execution timed out 1080 ms 15144 KB Time limit exceeded
10 Execution timed out 1069 ms 15144 KB Time limit exceeded
11 Execution timed out 1073 ms 15144 KB Time limit exceeded
12 Incorrect 81 ms 15244 KB Output isn't correct
13 Incorrect 122 ms 15244 KB Output isn't correct

Subtask #2
10.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 15244 KB Output is correct
2 Execution timed out 1070 ms 23636 KB Time limit exceeded
3 Correct 109 ms 23636 KB Output is correct
4 Execution timed out 1082 ms 23636 KB Time limit exceeded
5 Execution timed out 1047 ms 23636 KB Time limit exceeded
6 Execution timed out 1070 ms 23636 KB Time limit exceeded
7 Execution timed out 1069 ms 23636 KB Time limit exceeded
8 Correct 42 ms 23636 KB Output is correct
9 Execution timed out 1069 ms 24116 KB Time limit exceeded
10 Execution timed out 1072 ms 24116 KB Time limit exceeded
11 Incorrect 212 ms 24116 KB Output isn't correct
12 Incorrect 230 ms 24116 KB Output isn't correct
13 Correct 139 ms 24116 KB Output is correct
14 Correct 114 ms 24116 KB Output is correct

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 99 ms 24116 KB Output isn't correct
2 Incorrect 247 ms 24116 KB Output isn't correct
3 Correct 153 ms 24116 KB Output is correct
4 Incorrect 158 ms 24116 KB Output isn't correct
5 Incorrect 172 ms 24116 KB Output isn't correct
6 Incorrect 162 ms 24116 KB Output isn't correct
7 Incorrect 146 ms 24116 KB Output isn't correct
8 Correct 146 ms 24116 KB Output is correct
9 Incorrect 242 ms 24116 KB Output isn't correct
10 Incorrect 248 ms 24116 KB Output isn't correct
11 Incorrect 251 ms 24248 KB Output isn't correct
12 Incorrect 250 ms 24248 KB Output isn't correct
13 Correct 229 ms 25576 KB Output is correct
14 Incorrect 212 ms 25576 KB Output isn't correct

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1077 ms 25576 KB Time limit exceeded
2 Incorrect 218 ms 25576 KB Output isn't correct
3 Correct 159 ms 25576 KB Output is correct
4 Execution timed out 1069 ms 25576 KB Time limit exceeded
5 Execution timed out 1070 ms 25576 KB Time limit exceeded
6 Incorrect 183 ms 25576 KB Output isn't correct
7 Incorrect 220 ms 25576 KB Output isn't correct
8 Correct 159 ms 25576 KB Output is correct
9 Correct 121 ms 25576 KB Output is correct