oj.uz

답안 #336501

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
336501 2020-12-15T13:08:08 Z Lecii Ball Machine (BOI13_ballmachine) C++14
29.8962 / 100
 1000 ms 30444 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],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;
    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
5.76923076923 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 5100 KB Output isn't correct
2 Incorrect 317 ms 12652 KB Output isn't correct
3 Correct 301 ms 12652 KB Output is correct
4 Correct 3 ms 5100 KB Output is 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 25 ms 5484 KB Output isn't correct
10 Incorrect 62 ms 6892 KB Output isn't correct
11 Incorrect 313 ms 12524 KB Output isn't correct
12 Correct 306 ms 12652 KB Output is correct
13 Incorrect 307 ms 12524 KB Output isn't correct

Subtask #2
23.5714285714 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1089 ms 9824 KB Time limit exceeded
2 Correct 389 ms 22600 KB Output is correct
3 Correct 303 ms 16112 KB Output is correct
4 Correct 228 ms 10732 KB Output is correct
5 Correct 238 ms 10732 KB Output is correct
6 Correct 246 ms 10476 KB Output is correct
7 Correct 227 ms 9272 KB Output is correct
8 Execution timed out 1052 ms 9740 KB Time limit exceeded
9 Correct 362 ms 23532 KB Output is correct
10 Correct 390 ms 22764 KB Output is correct
11 Correct 709 ms 22792 KB Output is correct
12 Correct 381 ms 19692 KB Output is correct
13 Execution timed out 1091 ms 27116 KB Time limit exceeded
14 Correct 297 ms 16060 KB Output is correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 174 ms 14304 KB Output isn't correct
2 Incorrect 382 ms 19948 KB Output isn't correct
3 Incorrect 259 ms 25324 KB Output isn't correct
4 Incorrect 232 ms 19820 KB Output isn't correct
5 Incorrect 245 ms 19308 KB Output isn't correct
6 Incorrect 239 ms 19308 KB Output isn't correct
7 Incorrect 237 ms 16876 KB Output isn't correct
8 Incorrect 261 ms 25324 KB Output isn't correct
9 Incorrect 370 ms 23532 KB Output isn't correct
10 Incorrect 369 ms 22764 KB Output isn't correct
11 Incorrect 363 ms 22636 KB Output isn't correct
12 Incorrect 360 ms 19948 KB Output isn't correct
13 Incorrect 392 ms 30444 KB Output isn't correct
14 Incorrect 320 ms 16100 KB Output isn't correct

Subtask #4
0.555555555556 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 373 ms 23660 KB Output isn't correct
2 Incorrect 379 ms 20076 KB Output isn't correct
3 Execution timed out 1049 ms 30068 KB Time limit exceeded
4 Incorrect 377 ms 23532 KB Output isn't correct
5 Incorrect 370 ms 22740 KB Output isn't correct
6 Incorrect 557 ms 22804 KB Output isn't correct
7 Incorrect 362 ms 19948 KB Output isn't correct
8 Execution timed out 1081 ms 30188 KB Time limit exceeded
9 Correct 305 ms 15972 KB Output is correct