oj.uz

Submission #199961

# Submission time Handle Problem Language Result Execution time Memory
199961 2020-02-04T14:09:16 Z dvdg6566 Ball Machine (BOI13_ballmachine) C++14
92.1429 / 100
 290 ms 25592 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
typedef pair<ll,pi> pii;
typedef vector<pi> vpi;
typedef set<ll> si;
typedef long double ld;
#define mp make_pair
#define pb push_back
#define f first
#define s second
ll INF = 1e18;
ll MOD = 1e9+7;
#define lb lower_bound
#define ub upper_bound
#define SZ(x) (ll)x.size()
#define ALL(x) x.begin(),x.end()


vi adjList[100100];
int p[100100][18];
int N,Q,a,b,root;
int depth[100100],cnt=1;
int preorder[100100], ind[100100];
bool clear[100100];
set<int> MS;
int low[100100];

void d1(int x){
  low[x] = x;
  for (auto i : adjList[x]){
    d1(i);
    low[x] = min(low[x], low[i]);
  }
}

void dfs(int x, int u){
  // cout<<x<<' '<<u<<'\n';
    for (auto i : adjList[x]){
      depth[i] = depth[x] + 1;
      dfs(i, x);
    }
    preorder[cnt] = x;
    ind[x] = cnt;
    cnt++;
}

void d2(int x){
  for (auto i : adjList[x]){
    p[ind[i]][0] = ind[x];
    d2(i);
  }
}

int find_clear(int x){
  // for (int i=1;i<=N;++i)cout<<clear[i]<<' ';cout<<'\n';
  for (int i=17;i>=0;--i){
    if (!clear[p[x][i]]){
      // cout<<x<<' '<<p[x][i]<<'\n';
      x = p[x][i];
    }
  }
  // cout<<"Top "<<x<<'\n';
  return x;
}

bool cmp(int a, int b){
  return low[a] < low[b];
}

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  // freopen("input.txt","r",stdin);
  cin>>N>>Q;
  memset(p,0,sizeof(p));
  for (int i=1;i<=N;++i){
    MS.insert(i);
    cin>>a;
    if (a == 0)root=i;
    else {
      adjList[a].pb(i);
    }
  }
  d1(root);
  // for (int i=1;i<=N;++i)cout<<low[i]<<' ';cout<<'\n';
  for (int i=1;i<=N;++i)sort(ALL(adjList[i]), cmp);
  for (int i=0;i<=N;++i)clear[i] = 1;
  dfs(root, 0);
  d2(root);
  // for (int i=1;i<=N;++i)cout<<i<<' '<<preorder[i]<<' '<<p[i][0]<<'\n';
    for (int i = 1; i <= 17; i++){
      for (int j = 1; j <= N; j++){
        if (p[j][i-1] == -1) p[j][i] = -1;
        else p[j][i]=p[p[j][i-1]][i-1];
     }
   }
    for (int i=0;i<Q;++i){
      cin>>a>>b;
      if (a == 1){
        int x;
         for (int i=0;i<b;++i){
           x = *MS.begin();
           MS.erase(x);
           clear[x] = 0;
           // cout << "Fill " << x << '\n';
         } 
         cout << preorder[x] << '\n';
      }else{
        int x = find_clear(ind[b]);
        cout << depth[b] - depth[preorder[x]] <<'\n';
        clear[x] = 1;
        // cout << "clearing " << x << '\n';
        MS.insert(x);
      }
    }
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:110:33: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
          cout << preorder[x] << '\n';
                                 ^~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9848 KB Output is correct
2 Correct 138 ms 16376 KB Output is correct
3 Correct 104 ms 16376 KB Output is correct
4 Correct 10 ms 9852 KB Output is correct
5 Correct 10 ms 9848 KB Output is correct
6 Correct 11 ms 9848 KB Output is correct
7 Correct 10 ms 9848 KB Output is correct
8 Correct 11 ms 9848 KB Output is correct
9 Correct 16 ms 10232 KB Output is correct
10 Correct 32 ms 11256 KB Output is correct
11 Correct 158 ms 16252 KB Output is correct
12 Correct 91 ms 16376 KB Output is correct
13 Correct 118 ms 16248 KB Output is correct

Subtask #2
27.8571428571 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 13176 KB Output is correct
2 Correct 240 ms 21984 KB Output is correct
3 Correct 114 ms 18884 KB Output is correct
4 Correct 86 ms 14072 KB Output is correct
5 Correct 88 ms 13944 KB Output is correct
6 Correct 77 ms 13944 KB Output is correct
7 Correct 78 ms 13304 KB Output is correct
8 Correct 48 ms 13176 KB Output is correct
9 Correct 176 ms 22392 KB Output is correct
10 Correct 218 ms 21880 KB Output is correct
11 Correct 176 ms 21880 KB Output is correct
12 Correct 199 ms 20600 KB Output is correct
13 Correct 151 ms 23800 KB Output is correct
14 Execution timed out 102 ms 18800 KB Time limit exceeded (wall clock)

Subtask #3
34.2857142857 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 16248 KB Output is correct
2 Execution timed out 35 ms 14840 KB Time limit exceeded (wall clock)
3 Execution timed out 116 ms 22136 KB Time limit exceeded (wall clock)
4 Correct 145 ms 19828 KB Output is correct
5 Correct 159 ms 19576 KB Output is correct
6 Correct 146 ms 19576 KB Output is correct
7 Correct 163 ms 18604 KB Output is correct
8 Correct 189 ms 22392 KB Output is correct
9 Correct 269 ms 22520 KB Output is correct
10 Correct 290 ms 22300 KB Output is correct
11 Correct 265 ms 22008 KB Output is correct
12 Correct 262 ms 20832 KB Output is correct
13 Correct 250 ms 25592 KB Output is correct
14 Correct 226 ms 19032 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 22560 KB Output is correct
2 Correct 243 ms 20856 KB Output is correct
3 Correct 174 ms 25444 KB Output is correct
4 Correct 223 ms 22640 KB Output is correct
5 Correct 247 ms 22116 KB Output is correct
6 Correct 242 ms 22008 KB Output is correct
7 Correct 245 ms 20924 KB Output is correct
8 Correct 185 ms 25464 KB Output is correct
9 Correct 126 ms 18904 KB Output is correct