oj.uz

Submission #42663

# Submission time Handle Problem Language Result Execution time Memory
42663 2018-03-01T23:58:19 Z XmtosX Ball Machine (BOI13_ballmachine) C++14
20.9524 / 100
 257 ms 25672 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--&&!s.empty())
            {
                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 Incorrect 3 ms 2808 KB Output isn't correct
2 Incorrect 146 ms 14816 KB Output isn't correct
3 Incorrect 83 ms 15020 KB Output isn't correct
4 Incorrect 3 ms 15020 KB Output isn't correct
5 Incorrect 3 ms 15020 KB Output isn't correct
6 Incorrect 4 ms 15020 KB Output isn't correct
7 Incorrect 4 ms 15020 KB Output isn't correct
8 Incorrect 4 ms 15020 KB Output isn't correct
9 Incorrect 10 ms 15020 KB Output isn't correct
10 Incorrect 28 ms 15020 KB Output isn't correct
11 Incorrect 147 ms 15112 KB Output isn't correct
12 Incorrect 79 ms 15244 KB Output isn't correct
13 Incorrect 121 ms 15244 KB Output isn't correct

Subtask #2
10.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 15244 KB Output is correct
2 Incorrect 222 ms 24464 KB Output isn't correct
3 Correct 109 ms 24464 KB Output is correct
4 Incorrect 96 ms 24464 KB Output isn't correct
5 Incorrect 107 ms 24464 KB Output isn't correct
6 Incorrect 79 ms 24464 KB Output isn't correct
7 Incorrect 88 ms 24464 KB Output isn't correct
8 Correct 45 ms 24464 KB Output is correct
9 Incorrect 207 ms 24644 KB Output isn't correct
10 Incorrect 221 ms 24644 KB Output isn't correct
11 Incorrect 220 ms 24644 KB Output isn't correct
12 Incorrect 237 ms 24644 KB Output isn't correct
13 Correct 151 ms 24644 KB Output is correct
14 Correct 107 ms 24644 KB Output is correct

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 105 ms 24644 KB Output isn't correct
2 Incorrect 256 ms 24644 KB Output isn't correct
3 Correct 148 ms 24644 KB Output is correct
4 Incorrect 146 ms 24644 KB Output isn't correct
5 Incorrect 151 ms 24644 KB Output isn't correct
6 Incorrect 161 ms 24644 KB Output isn't correct
7 Incorrect 160 ms 24644 KB Output isn't correct
8 Correct 143 ms 24644 KB Output is correct
9 Incorrect 251 ms 24644 KB Output isn't correct
10 Incorrect 255 ms 24644 KB Output isn't correct
11 Incorrect 257 ms 24644 KB Output isn't correct
12 Incorrect 228 ms 24644 KB Output isn't correct
13 Correct 231 ms 25644 KB Output is correct
14 Incorrect 201 ms 25644 KB Output isn't correct

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 205 ms 25644 KB Output isn't correct
2 Incorrect 232 ms 25644 KB Output isn't correct
3 Correct 149 ms 25672 KB Output is correct
4 Incorrect 202 ms 25672 KB Output isn't correct
5 Incorrect 214 ms 25672 KB Output isn't correct
6 Incorrect 200 ms 25672 KB Output isn't correct
7 Incorrect 234 ms 25672 KB Output isn't correct
8 Correct 156 ms 25672 KB Output is correct
9 Correct 126 ms 25672 KB Output is correct