oj.uz

Submission #336498

# Submission time Handle Problem Language Result Execution time Memory
336498 2020-12-15T12:58:48 Z Lecii Ball Machine (BOI13_ballmachine) C++14
0 / 100
 1000 ms 30316 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

int n,m;
int u,v;
vector<int> g[100005];
vector<pii> g2[100005];
int root;
int mi[100005];
bool a[100005];
int d[100005];
int pa[100005][18];
int las;

void dfs(int u,int dis)
{
    d[u]=dis;
    mi[u]=u;
    for(int i=0;i<(int)g[u].size();i++)
    {
        pa[g[u][i]][0]=u;
        dfs(g[u][i],dis+1);
        mi[u]=min(mi[u],g[u][i]);
        g2[u].push_back({mi[g[u][i]],g[u][i]});
    }
    sort(g2[u].begin(),g2[u].end());
}
int dfs2(int u,int b)
{
    if(b<=0) return 0;
    for(int i=0;i<(int)g2[u].size();i++)
    {
        if(!a[g2[u][i].second]) b=dfs2(g2[u][i].second,b);
        if(b<=0) return 0;
    }
    a[u]=1;
    las=u;
    --b;
    return b;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>u;
        if(u==0) root=i;
        else
            g[u].push_back(i);
    }
    pa[root][0]=root;
    dfs(root,0);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=17;j++) pa[i][j]=pa[pa[i][j-1]][j-1];

    while(m--)
    {
        cin>>u>>v;
        if(u==1)
        {
            dfs2(root,v);
            cout<<las<<endl;
        }
        else
        {
            int u=v;
            for(int i=17;i>=0;i--)
                if(a[pa[v][i]])
                    v=pa[v][i];
            a[v]=0;
            cout<<d[u]-d[v]<<endl;
        }
    }
    return 0;
}

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 5100 KB Output isn't correct
2 Incorrect 328 ms 12652 KB Output isn't correct
3 Incorrect 313 ms 12780 KB Output isn't correct
4 Incorrect 4 ms 5100 KB Output isn't correct
5 Incorrect 5 ms 5100 KB Output isn't correct
6 Incorrect 5 ms 5228 KB Output isn't correct
7 Incorrect 6 ms 5228 KB Output isn't correct
8 Incorrect 7 ms 5228 KB Output isn't correct
9 Incorrect 25 ms 5484 KB Output isn't correct
10 Incorrect 65 ms 6892 KB Output isn't correct
11 Incorrect 311 ms 12524 KB Output isn't correct
12 Incorrect 303 ms 12652 KB Output isn't correct
13 Incorrect 318 ms 12652 KB Output isn't correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1044 ms 9708 KB Time limit exceeded
2 Incorrect 376 ms 22764 KB Output isn't correct
3 Execution timed out 1060 ms 16448 KB Time limit exceeded
4 Incorrect 232 ms 10860 KB Output isn't correct
5 Incorrect 233 ms 10476 KB Output isn't correct
6 Incorrect 236 ms 10476 KB Output isn't correct
7 Incorrect 227 ms 9324 KB Output isn't correct
8 Execution timed out 1086 ms 9708 KB Time limit exceeded
9 Incorrect 378 ms 23532 KB Output isn't correct
10 Incorrect 376 ms 22680 KB Output isn't correct
11 Incorrect 598 ms 22636 KB Output isn't correct
12 Incorrect 369 ms 19564 KB Output isn't correct
13 Execution timed out 1052 ms 27244 KB Time limit exceeded
14 Execution timed out 1068 ms 16612 KB Time limit exceeded

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 177 ms 14316 KB Output isn't correct
2 Incorrect 365 ms 19948 KB Output isn't correct
3 Incorrect 252 ms 25324 KB Output isn't correct
4 Incorrect 235 ms 19820 KB Output isn't correct
5 Incorrect 233 ms 19180 KB Output isn't correct
6 Incorrect 234 ms 19200 KB Output isn't correct
7 Incorrect 233 ms 16876 KB Output isn't correct
8 Incorrect 256 ms 25324 KB Output isn't correct
9 Incorrect 376 ms 23532 KB Output isn't correct
10 Incorrect 383 ms 22764 KB Output isn't correct
11 Incorrect 374 ms 22636 KB Output isn't correct
12 Incorrect 367 ms 20076 KB Output isn't correct
13 Incorrect 398 ms 30316 KB Output isn't correct
14 Incorrect 325 ms 16240 KB Output isn't correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 370 ms 23532 KB Output isn't correct
2 Incorrect 397 ms 20076 KB Output isn't correct
3 Execution timed out 1065 ms 30060 KB Time limit exceeded
4 Incorrect 371 ms 23532 KB Output isn't correct
5 Incorrect 370 ms 22764 KB Output isn't correct
6 Incorrect 591 ms 22892 KB Output isn't correct
7 Incorrect 366 ms 19948 KB Output isn't correct
8 Execution timed out 1096 ms 30060 KB Time limit exceeded
9 Incorrect 729 ms 16356 KB Output isn't correct