oj.uz

답안 #77368

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
77368 2018-09-26T21:40:39 Z xiaowuc1 Ball Machine (BOI13_ballmachine) C++14
16.1111 / 100
 947 ms 64076 KB 
#include <bits/stdc++.h>

/*
unsigned seed1 = std::chrono::system_clock::now().time_since_epoch().count();
mt19937 g1.seed(seed1);

ios_base::sync_with_stdio(false);
cin.tie(NULL);
*/
using namespace std;

const double PI = 2 * acos(0);

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<vector<ll>> matrix;

typedef pair<int, bool> pib;

const int MAX_N = 100000+1;
const int MAX_D = 16;
int lca[MAX_D][MAX_N];
int depth[MAX_N];
vector<int> children[MAX_N];
int n;
int root;

int vertexOrder[MAX_N];
int _order;

bool ordercmp(int a, int b) {
  return vertexOrder[a] < vertexOrder[b];
}

set<int, bool(*)(int, int)> avail(ordercmp);

void solve() {
  int t;
  scanf("%d", &t);
  int k;
  if(t == 1) {
    // insert k
    scanf("%d", &k);
    int last;
    while(k--) {
      last = *avail.begin();
      avail.erase(last);
    }
    printf("%d\n", last);
  }
  else {
    // remove from k
    scanf("%d", &k);
    int ret = 0;
    for(int d = MAX_D-1; d >= 0; d--) {
      while(depth[k] >= (1<<d) && !avail.count(lca[d][k])) {
        k = lca[d][k];
        ret += 1 << d;
      }
    }
    avail.insert(k);
    printf("%d\n", ret);
  }
}

void genOrder() {
  stack<pib> s;
  s.push(pib(root, false));
  while(!s.empty()) {
    pib curr = s.top();
    s.pop();
    if(curr.second) {
      vertexOrder[curr.first] = _order++;
    }
    else {
      s.push(pib(curr.first, true));
      for(int out: children[curr.first]) {
        s.push(pib(out, false));
      }
    }
  }
}

void genLCA() {
  queue<int> q;
  q.push(root);
  while(!q.empty()) {
    int curr = q.front();
    q.pop();
    sort(children[curr].begin(), children[curr].end());
    reverse(children[curr].begin(), children[curr].end());
    for(int out: children[curr]) {
      depth[out] = depth[curr]+1;
      q.push(out);
    }
  }
  for(int d = 1; d < MAX_D; d++) {
    for(int i = 1; i <= n; i++) {
      lca[d][i] = lca[d-1][lca[d-1][i]];
    }
  }
}

int main() {
  int q;
  scanf("%d%d", &n, &q);
  for(int i = 1; i <= n; i++) {
    scanf("%d", &lca[0][i]);
    if(lca[0][i]) {
      children[lca[0][i]].push_back(i);
    }
    else {
      root = i;
    }
  }
  genLCA();
  genOrder();
  for(int i = 1; i <= n; i++) {
    avail.insert(i);
  }
  while(q--) solve();
}

Compilation message

ballmachine.cpp: In function 'void solve()':
ballmachine.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &t);
   ~~~~~^~~~~~~~~~
ballmachine.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &k);
     ~~~~~^~~~~~~~~~
ballmachine.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &k);
     ~~~~~^~~~~~~~~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:109:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &n, &q);
   ~~~~~^~~~~~~~~~~~~~~~
ballmachine.cpp:111:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &lca[0][i]);
     ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 2808 KB Output isn't correct
2 Incorrect 270 ms 13044 KB Output isn't correct
3 Incorrect 134 ms 14156 KB Output isn't correct
4 Incorrect 4 ms 14156 KB Output isn't correct
5 Incorrect 5 ms 14156 KB Output isn't correct
6 Incorrect 5 ms 14156 KB Output isn't correct
7 Incorrect 5 ms 14156 KB Output isn't correct
8 Incorrect 6 ms 14156 KB Output isn't correct
9 Incorrect 16 ms 14156 KB Output isn't correct
10 Incorrect 49 ms 14156 KB Output isn't correct
11 Incorrect 282 ms 15720 KB Output isn't correct
12 Incorrect 124 ms 16844 KB Output isn't correct
13 Incorrect 225 ms 17740 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 17740 KB Output is correct
2 Incorrect 777 ms 24768 KB Output isn't correct
3 Incorrect 140 ms 25068 KB Output isn't correct
4 Incorrect 238 ms 25068 KB Output isn't correct
5 Incorrect 348 ms 25068 KB Output isn't correct
6 Incorrect 323 ms 25068 KB Output isn't correct
7 Incorrect 298 ms 25068 KB Output isn't correct
8 Correct 90 ms 25068 KB Output is correct
9 Incorrect 539 ms 31000 KB Output isn't correct
10 Incorrect 776 ms 32008 KB Output isn't correct
11 Incorrect 572 ms 33376 KB Output isn't correct
12 Incorrect 710 ms 34472 KB Output isn't correct
13 Correct 214 ms 35368 KB Output is correct
14 Incorrect 153 ms 36352 KB Output isn't correct

Subtask #3
8.57142857143 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 224 ms 36352 KB Output isn't correct
2 Incorrect 753 ms 38780 KB Output isn't correct
3 Correct 432 ms 38780 KB Output is correct
4 Incorrect 385 ms 38780 KB Output isn't correct
5 Incorrect 511 ms 38780 KB Output isn't correct
6 Incorrect 501 ms 39572 KB Output isn't correct
7 Incorrect 476 ms 40584 KB Output isn't correct
8 Correct 431 ms 42496 KB Output is correct
9 Incorrect 558 ms 46120 KB Output isn't correct
10 Incorrect 751 ms 47068 KB Output isn't correct
11 Incorrect 763 ms 48512 KB Output isn't correct
12 Incorrect 735 ms 49752 KB Output isn't correct
13 Correct 712 ms 52368 KB Output is correct
14 Incorrect 242 ms 52368 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 741 ms 54148 KB Output isn't correct
2 Incorrect 874 ms 55204 KB Output isn't correct
3 Correct 237 ms 57412 KB Output is correct
4 Incorrect 822 ms 58216 KB Output isn't correct
5 Incorrect 947 ms 58960 KB Output isn't correct
6 Incorrect 683 ms 60364 KB Output isn't correct
7 Incorrect 850 ms 61768 KB Output isn't correct
8 Correct 235 ms 64076 KB Output is correct
9 Incorrect 138 ms 64076 KB Output isn't correct