oj.uz

Submission #336497

# Submission time Handle Problem Language Result Execution time Memory
336497 2020-12-15T12:57:30 Z Lecii Ball Machine (BOI13_ballmachine) C++14
0 / 100
 1000 ms 31852 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<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<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;
}

Compilation message

ballmachine.cpp: In function 'void dfs(int, int)':
ballmachine.cpp:20:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(int i=0;i<g[u].size();i++)
      |                 ~^~~~~~~~~~~~
ballmachine.cpp: In function 'int dfs2(int, int)':
ballmachine.cpp:32:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int i=0;i<g2[u].size();i++)
      |                 ~^~~~~~~~~~~~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 5100 KB Output isn't correct
2 Incorrect 318 ms 13676 KB Output isn't correct
3 Incorrect 311 ms 13676 KB Output isn't correct
4 Incorrect 4 ms 5100 KB Output isn't correct
5 Incorrect 4 ms 5100 KB Output isn't correct
6 Incorrect 5 ms 5228 KB Output isn't correct
7 Incorrect 7 ms 5228 KB Output isn't correct
8 Incorrect 7 ms 5228 KB Output isn't correct
9 Incorrect 26 ms 5612 KB Output isn't correct
10 Incorrect 64 ms 7148 KB Output isn't correct
11 Incorrect 325 ms 13676 KB Output isn't correct
12 Incorrect 308 ms 13828 KB Output isn't correct
13 Incorrect 315 ms 13784 KB Output isn't correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1046 ms 10240 KB Time limit exceeded
2 Incorrect 368 ms 24044 KB Output isn't correct
3 Execution timed out 1048 ms 17380 KB Time limit exceeded
4 Incorrect 233 ms 11500 KB Output isn't correct
5 Incorrect 232 ms 11264 KB Output isn't correct
6 Incorrect 233 ms 11244 KB Output isn't correct
7 Incorrect 238 ms 10092 KB Output isn't correct
8 Execution timed out 1098 ms 10220 KB Time limit exceeded
9 Incorrect 370 ms 24812 KB Output isn't correct
10 Incorrect 364 ms 24044 KB Output isn't correct
11 Incorrect 590 ms 24080 KB Output isn't correct
12 Incorrect 369 ms 20980 KB Output isn't correct
13 Execution timed out 1092 ms 27884 KB Time limit exceeded
14 Execution timed out 1087 ms 17536 KB Time limit exceeded

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 213 ms 15084 KB Output isn't correct
2 Incorrect 374 ms 21500 KB Output isn't correct
3 Incorrect 255 ms 26276 KB Output isn't correct
4 Incorrect 228 ms 20716 KB Output isn't correct
5 Incorrect 231 ms 20076 KB Output isn't correct
6 Incorrect 237 ms 20076 KB Output isn't correct
7 Incorrect 240 ms 17916 KB Output isn't correct
8 Incorrect 250 ms 26220 KB Output isn't correct
9 Incorrect 373 ms 24940 KB Output isn't correct
10 Incorrect 367 ms 24044 KB Output isn't correct
11 Incorrect 378 ms 24216 KB Output isn't correct
12 Incorrect 364 ms 21356 KB Output isn't correct
13 Incorrect 397 ms 31852 KB Output isn't correct
14 Incorrect 324 ms 17508 KB Output isn't correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 369 ms 24812 KB Output isn't correct
2 Incorrect 376 ms 21356 KB Output isn't correct
3 Execution timed out 1089 ms 30828 KB Time limit exceeded
4 Incorrect 365 ms 24812 KB Output isn't correct
5 Incorrect 369 ms 24172 KB Output isn't correct
6 Incorrect 584 ms 24044 KB Output isn't correct
7 Incorrect 368 ms 21228 KB Output isn't correct
8 Execution timed out 1086 ms 30828 KB Time limit exceeded
9 Incorrect 732 ms 17124 KB Output isn't correct