oj.uz

Submission #336508

# Submission time Handle Problem Language Result Execution time Memory
336508 2020-12-15T13:21:34 Z Lecii Ball Machine (BOI13_ballmachine) C++14
51.9841 / 100
 1000 ms 30980 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 L;
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],mi[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.tie(0); cout.tie(0);
    cin>>n>>m;
    L=__lg(n)+2;
    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 j=1;j<=L;j++)
        for(int i=1;i<=n;i++)
            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=L;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:21:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for(int i=0;i<g[u].size();i++)
      |                 ~^~~~~~~~~~~~
ballmachine.cpp: In function 'int dfs2(int, int)':
ballmachine.cpp:33: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]
   33 |     for(int i=0;i<g2[u].size();i++)
      |                 ~^~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 308 ms 12524 KB Output is correct
3 Correct 298 ms 12652 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 4 ms 5100 KB Output is correct
6 Correct 5 ms 5228 KB Output is correct
7 Correct 6 ms 5228 KB Output is correct
8 Correct 7 ms 5228 KB Output is correct
9 Correct 25 ms 5484 KB Output is correct
10 Correct 61 ms 6892 KB Output is correct
11 Correct 308 ms 12524 KB Output is correct
12 Correct 296 ms 12652 KB Output is correct
13 Correct 305 ms 12664 KB Output is correct

Subtask #2
23.5714285714 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1059 ms 9836 KB Time limit exceeded
2 Correct 370 ms 22636 KB Output is correct
3 Correct 294 ms 15972 KB Output is correct
4 Correct 231 ms 10732 KB Output is correct
5 Correct 234 ms 10476 KB Output is correct
6 Correct 248 ms 10476 KB Output is correct
7 Correct 235 ms 9324 KB Output is correct
8 Execution timed out 1088 ms 9964 KB Time limit exceeded
9 Correct 368 ms 23532 KB Output is correct
10 Correct 377 ms 22764 KB Output is correct
11 Correct 748 ms 22764 KB Output is correct
12 Correct 375 ms 19692 KB Output is correct
13 Execution timed out 1088 ms 27116 KB Time limit exceeded
14 Correct 298 ms 16104 KB Output is correct

Subtask #3
2.85714285714 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 14316 KB Output is correct
2 Incorrect 394 ms 20076 KB Output isn't correct
3 Incorrect 269 ms 25640 KB Output isn't correct
4 Incorrect 244 ms 20076 KB Output isn't correct
5 Incorrect 241 ms 19180 KB Output isn't correct
6 Incorrect 245 ms 19308 KB Output isn't correct
7 Incorrect 240 ms 17004 KB Output isn't correct
8 Incorrect 273 ms 25580 KB Output isn't correct
9 Incorrect 383 ms 23660 KB Output isn't correct
10 Incorrect 388 ms 22892 KB Output isn't correct
11 Incorrect 392 ms 22892 KB Output isn't correct
12 Incorrect 392 ms 20204 KB Output isn't correct
13 Incorrect 463 ms 30980 KB Output isn't correct
14 Incorrect 332 ms 16228 KB Output isn't correct

Subtask #4
0.555555555556 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 415 ms 23788 KB Output isn't correct
2 Incorrect 462 ms 20076 KB Output isn't correct
3 Execution timed out 1091 ms 30060 KB Time limit exceeded
4 Incorrect 450 ms 23916 KB Output isn't correct
5 Incorrect 409 ms 22892 KB Output isn't correct
6 Incorrect 796 ms 22892 KB Output isn't correct
7 Incorrect 389 ms 20204 KB Output isn't correct
8 Execution timed out 1082 ms 30060 KB Time limit exceeded
9 Correct 306 ms 15972 KB Output is correct