Submission #106441

# Submission time Handle Problem Language Result Execution time Memory
106441 2019-04-18T13:41:21 Z RedNextCentury Ball Machine (BOI13_ballmachine) C++14
0 / 100
520 ms 47456 KB
#include<bits/stdc++.h>
using namespace std;
vector<int> adj[1000000];
int mn[1000000];
bool cmp(int a,int b)
{
    return mn[a]<mn[b];
}
void pre(int v)
{
    mn[v]=v;
    for (auto u:adj[v])
    {
        pre(u);
        mn[v]=min(mn[v],mn[u]);
    }
}
int pa[1000001][21];
int ord[1000001];
int tt=1;
void dfs(int v)
{
    for (auto u:adj[v])
        dfs(u);
    ord[v]=tt++;
}
bool has[1000000];
int main()
{
    freopen("out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,q;
    cin>>n>>q;
    int root=-1;
    for (int i=1;i<=n;i++)
    {
        cin>>pa[i][0];
        if (pa[i][0]==0) root = i;
        else adj[pa[i][0]].push_back(i);
    }
    for (int j=1;j<=18;j++)
        for (int i=1;i<=n;i++)
            pa[i][j]=pa[pa[i][j-1]][j-1];
    pre(root);
    for (int i=1;i<=n;i++)
        sort(adj[i].begin(),adj[i].end(),cmp);
    dfs(root);
    set<pair<int,int> > s;
    for (int i=1;i<=n;i++)
        s.insert({ord[i],i});
    while(q--)
    {
        int t,v;
        cin>>t>>v;
        if (t==1)
        {
            pair<int,int> p;
            while(v--)
            {
                p = *s.begin();
                s.erase(s.begin());
                has[p.second]=1;
            }
            cout<<p.second<<endl;
        }
        else
        {
            int u = v;
            int ret=0;
            for (int i=18;i>=0;i--)
                if (has[pa[u][i]])
                    u = pa[u][i] , ret+=(1<<i);
            has[u]=0;
            s.insert({ord[u],u});
            cout<<ret<<endl;
        }
    }
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:30:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("out","w",stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 23936 KB Output isn't correct
2 Incorrect 368 ms 35192 KB Output isn't correct
3 Incorrect 282 ms 35384 KB Output isn't correct
4 Incorrect 24 ms 23936 KB Output isn't correct
5 Incorrect 29 ms 23928 KB Output isn't correct
6 Incorrect 25 ms 24064 KB Output isn't correct
7 Incorrect 26 ms 24056 KB Output isn't correct
8 Incorrect 27 ms 24064 KB Output isn't correct
9 Incorrect 44 ms 24576 KB Output isn't correct
10 Incorrect 105 ms 26804 KB Output isn't correct
11 Incorrect 388 ms 35192 KB Output isn't correct
12 Incorrect 272 ms 35192 KB Output isn't correct
13 Incorrect 379 ms 35432 KB Output isn't correct
# Verdict Execution time Memory Grader output
1 Incorrect 179 ms 28660 KB Output isn't correct
2 Incorrect 446 ms 43480 KB Output isn't correct
3 Incorrect 288 ms 40048 KB Output isn't correct
4 Incorrect 252 ms 30488 KB Output isn't correct
5 Incorrect 247 ms 30328 KB Output isn't correct
6 Incorrect 214 ms 30200 KB Output isn't correct
7 Incorrect 240 ms 29600 KB Output isn't correct
8 Incorrect 178 ms 28536 KB Output isn't correct
9 Incorrect 413 ms 44148 KB Output isn't correct
10 Incorrect 434 ms 43488 KB Output isn't correct
11 Incorrect 401 ms 43512 KB Output isn't correct
12 Incorrect 477 ms 41848 KB Output isn't correct
13 Incorrect 347 ms 44452 KB Output isn't correct
14 Incorrect 295 ms 40052 KB Output isn't correct
# Verdict Execution time Memory Grader output
1 Incorrect 244 ms 34136 KB Output isn't correct
2 Incorrect 520 ms 42488 KB Output isn't correct
3 Incorrect 339 ms 42672 KB Output isn't correct
4 Incorrect 301 ms 39800 KB Output isn't correct
5 Incorrect 369 ms 39620 KB Output isn't correct
6 Incorrect 356 ms 39544 KB Output isn't correct
7 Incorrect 330 ms 38648 KB Output isn't correct
8 Incorrect 303 ms 42448 KB Output isn't correct
9 Incorrect 516 ms 44280 KB Output isn't correct
10 Incorrect 470 ms 43640 KB Output isn't correct
11 Incorrect 505 ms 43768 KB Output isn't correct
12 Incorrect 503 ms 42616 KB Output isn't correct
13 Incorrect 501 ms 47456 KB Output isn't correct
14 Incorrect 480 ms 40828 KB Output isn't correct
# Verdict Execution time Memory Grader output
1 Incorrect 463 ms 44224 KB Output isn't correct
2 Incorrect 480 ms 42504 KB Output isn't correct
3 Incorrect 358 ms 46968 KB Output isn't correct
4 Incorrect 473 ms 44308 KB Output isn't correct
5 Incorrect 460 ms 43768 KB Output isn't correct
6 Incorrect 419 ms 43704 KB Output isn't correct
7 Incorrect 486 ms 42844 KB Output isn't correct
8 Incorrect 367 ms 46968 KB Output isn't correct
9 Incorrect 338 ms 40180 KB Output isn't correct