oj.uz

Submission #336511

# Submission time Handle Problem Language Result Execution time Memory
336511 2020-12-15T13:40:02 Z Lecii Ball Machine (BOI13_ballmachine) C++14
92.4603 / 100
 1000 ms 33772 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][25];
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]});
    }
    if(!g2[u].empty())
        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)+5;
    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:34: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]
   34 |     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 316 ms 14372 KB Output is correct
3 Correct 304 ms 14444 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 4 ms 5100 KB Output is correct
6 Correct 6 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 5612 KB Output is correct
10 Correct 62 ms 7404 KB Output is correct
11 Correct 312 ms 14316 KB Output is correct
12 Correct 308 ms 14456 KB Output is correct
13 Correct 307 ms 14316 KB Output is correct

Subtask #2
23.5714285714 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 10220 KB Time limit exceeded
2 Correct 375 ms 25580 KB Output is correct
3 Correct 316 ms 18788 KB Output is correct
4 Correct 234 ms 11628 KB Output is correct
5 Correct 238 ms 11244 KB Output is correct
6 Correct 250 ms 11232 KB Output is correct
7 Correct 244 ms 10340 KB Output is correct
8 Execution timed out 1090 ms 10220 KB Time limit exceeded
9 Correct 369 ms 26220 KB Output is correct
10 Correct 383 ms 25452 KB Output is correct
11 Correct 698 ms 25344 KB Output is correct
12 Correct 372 ms 22252 KB Output is correct
13 Execution timed out 1094 ms 29548 KB Time limit exceeded
14 Correct 314 ms 19044 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 15852 KB Output is correct
2 Correct 400 ms 22892 KB Output is correct
3 Correct 274 ms 27756 KB Output is correct
4 Correct 246 ms 22124 KB Output is correct
5 Correct 244 ms 21484 KB Output is correct
6 Correct 251 ms 21484 KB Output is correct
7 Correct 249 ms 19180 KB Output is correct
8 Correct 275 ms 27756 KB Output is correct
9 Correct 396 ms 26476 KB Output is correct
10 Correct 390 ms 25708 KB Output is correct
11 Correct 395 ms 25708 KB Output is correct
12 Correct 394 ms 23020 KB Output is correct
13 Correct 435 ms 33772 KB Output is correct
14 Correct 331 ms 18916 KB Output is correct

Subtask #4
3.88888888889 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 428 ms 26604 KB Output is correct
2 Correct 395 ms 22892 KB Output is correct
3 Execution timed out 1093 ms 32876 KB Time limit exceeded
4 Correct 407 ms 26732 KB Output is correct
5 Correct 406 ms 25580 KB Output is correct
6 Correct 818 ms 25836 KB Output is correct
7 Correct 400 ms 22892 KB Output is correct
8 Execution timed out 1052 ms 32876 KB Time limit exceeded
9 Correct 306 ms 18916 KB Output is correct