oj.uz

Submission #71842

# Submission time Handle Problem Language Result Execution time Memory
71842 2018-08-25T16:54:53 Z doowey Ball Machine (BOI13_ballmachine) C++14
47.8755 / 100
 278 ms 49408 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef long double db;
typedef pair<int,int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO std::ios::sync_with_stdio(false);cin.tie(NULL);
#define TEST freopen("in.txt","r",stdin);
#define ones(a) __builtin_popcount(a);
#define pq priority_queue

const int N = (int)1e5 + 9;
const int LOG = 18;
vector<int> T[N];
int min_leaf[N];
int up[N][LOG];

void dfs1(int node,int par){
  min_leaf[node] = 21344567;
  up[node][0] = par;
  for(int i = 1;i < LOG;i ++ ){
    if(up[node][i - 1] != -1)
      up[node][i] = up[up[node][i - 1]][i - 1];
  }
  for(auto x : T[node]){
    dfs1(x, node);
    min_leaf[node] = min(min_leaf[node], min_leaf[x]);
  }
  if(T[node].empty())
    min_leaf[node] = node;
}

int tt;
int porder[N];
int pos[N];
bool is[N]; 

void dfs2(int node){
  vector<pii> nex;
  porder[tt] = node;
  pos[node] = tt++;
  for(auto x : T[node])
    nex.push_back(mp(min_leaf[x], x));
  sort(nex.begin(), nex.end());
  for(int i = (int)nex.size() - 1;i >= 0;i -- ){
    dfs2(nex[i].se);
  }
}

pq<int> emp;

int ins(int k){
  int fr;
  for(int i = 0;i < k;i ++ ){
    fr = emp.top();
    emp.pop();
    is[porder[fr]] = true;
  }
  return porder[fr];
}

int rem(int ix){
  int sum = 0;
  int go = ix;
  for(int i = LOG-1;i >= 0 ;i -- ){
    if(up[go][i] == -1)
      continue;
    if(is[up[go][i]]){
      sum += (1 << i);
      go = up[go][i];
    }
  }
  is[go] = false;
  emp.push(pos[go]);
  return sum;
}

int main(){
  fastIO;
  memset(up, -1, sizeof up);
  int n, q;
  cin >> n >> q;
  for(int i = 0;i <= n;i ++ )
    is[i] = false;
  int x;
  int root;
  for(int i = 1;i <= n;i ++ ){
    cin >> x;
    if(x == 0)
      root = i;
    else
      T[x].push_back(i);
  }
  dfs1(root, -1);
  dfs2(root);
  for(int i = 0;i < tt;i ++ )
    emp.push(i);
  int ty, bl;
  for(int i = 0;i < q;i ++ ){
    cin >> ty >> bl;
    if(ty == 1)
      cout << ins(bl) << "\n";
    else
      cout << rem(bl) << "\n";
  }
  return 0;
}

Compilation message

ballmachine.cpp: In function 'int ins(int)':
ballmachine.cpp:60:7: warning: 'fr' may be used uninitialized in this function [-Wmaybe-uninitialized]
   int fr;
       ^~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:60:7: warning: 'fr' may be used uninitialized in this function [-Wmaybe-uninitialized]
ballmachine.cpp:102:7: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   dfs2(root);
   ~~~~^~~~~~

Subtask #1
1.92307692308 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 9720 KB Output isn't correct
2 Incorrect 124 ms 13436 KB Output isn't correct
3 Incorrect 95 ms 14632 KB Output isn't correct
4 Correct 12 ms 14632 KB Output is correct
5 Incorrect 10 ms 14632 KB Output isn't correct
6 Incorrect 13 ms 14632 KB Output isn't correct
7 Incorrect 11 ms 14632 KB Output isn't correct
8 Incorrect 12 ms 14632 KB Output isn't correct
9 Incorrect 17 ms 14632 KB Output isn't correct
10 Incorrect 33 ms 14632 KB Output isn't correct
11 Incorrect 141 ms 16000 KB Output isn't correct
12 Incorrect 88 ms 17140 KB Output isn't correct
13 Incorrect 103 ms 18216 KB Output isn't correct

Subtask #2
12.8571428571 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 18864 KB Output is correct
2 Incorrect 229 ms 26136 KB Output isn't correct
3 Correct 98 ms 26136 KB Output is correct
4 Incorrect 74 ms 26136 KB Output isn't correct
5 Incorrect 68 ms 26136 KB Output isn't correct
6 Incorrect 84 ms 26136 KB Output isn't correct
7 Incorrect 104 ms 26136 KB Output isn't correct
8 Correct 43 ms 26136 KB Output is correct
9 Incorrect 197 ms 30676 KB Output isn't correct
10 Incorrect 278 ms 31280 KB Output isn't correct
11 Incorrect 200 ms 31996 KB Output isn't correct
12 Correct 229 ms 31996 KB Output is correct
13 Correct 243 ms 38912 KB Output is correct
14 Correct 119 ms 38912 KB Output is correct

Subtask #3
31.4285714286 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 38912 KB Output is correct
2 Correct 239 ms 38912 KB Output is correct
3 Correct 214 ms 38912 KB Output is correct
4 Incorrect 131 ms 38912 KB Output isn't correct
5 Correct 157 ms 38912 KB Output is correct
6 Correct 136 ms 38912 KB Output is correct
7 Incorrect 127 ms 38912 KB Output isn't correct
8 Correct 170 ms 40064 KB Output is correct
9 Correct 235 ms 40064 KB Output is correct
10 Correct 227 ms 40064 KB Output is correct
11 Correct 255 ms 40064 KB Output is correct
12 Correct 200 ms 40064 KB Output is correct
13 Correct 257 ms 43904 KB Output is correct
14 Incorrect 137 ms 43904 KB Output isn't correct

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 199 ms 43904 KB Output isn't correct
2 Incorrect 209 ms 43904 KB Output isn't correct
3 Correct 211 ms 46172 KB Output is correct
4 Incorrect 230 ms 46172 KB Output isn't correct
5 Incorrect 208 ms 46172 KB Output isn't correct
6 Incorrect 188 ms 46172 KB Output isn't correct
7 Incorrect 182 ms 46172 KB Output isn't correct
8 Correct 172 ms 49408 KB Output is correct
9 Correct 105 ms 49408 KB Output is correct