oj.uz

답안 #102848

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
102848 2019-03-28T01:02:35 Z wxh010910 늑대인간 (IOI18_werewolf) C++17
100 / 100
 1883 ms 126920 KB 
#include <bits/stdc++.h>
#include "werewolf.h"

using namespace std;

template<typename T> class fenwick_t {
 public:
  vector<T> fenw;
  int n;

  fenwick_t(int n):n(n) {
    fenw.resize(n);
  }

  void modify(int x, T value) {
    while (x < n) {
      fenw[x] += value;
      x |= x + 1;
    }
  }

  T query(int x) {
    T result{};
    while (x >= 0) {
      result += fenw[x];
      x = (x & x + 1) - 1;
    }
    return result;
  }
};

vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r) {
  int m = x.size(), q = s.size();

  struct tree_t {
    struct edge_t {
      int u, v, w;

      edge_t(int u = 0, int v = 0, int w = 0):u(u), v(v), w(w) {
      }

      bool operator < (const edge_t &b) const {
        return w < b.w;
      }
    };

    vector<int> l, r, left, right, value;
    vector<vector<int>> ancestor;
    int n, log_n, total, counter;
    vector<edge_t> edge;
    
    tree_t(int n):n(n) {
      l = r = left = right = value = vector<int> ((n << 1) - 1, -1);
      total = n;
      log_n = counter = 0;
      while (1 << log_n <= n) {
        ++log_n;
      }
      ancestor = vector<vector<int>> (log_n, vector<int> ((n << 1) - 1, -1));
    }

    void dfs(int x) {
      left[x] = counter++;
      if (x >= n) {
        dfs(l[x]);
        dfs(r[x]);
      }
      right[x] = counter;
    }

    void init() {
      sort(edge.begin(), edge.end());
      vector<int> p((n << 1) - 1);
      for (int i = 0; i < (n << 1) - 1; ++i) {
        p[i] = i;
      }
      function<int(int)> find = [&](int x) {
        while (x != p[x]) {
          x = p[x] = p[p[x]];
        }
        return x;
      };
      
      total = n;
      for (auto e : edge) {
        if (find(e.u) != find(e.v)) {
          l[total] = find(e.u);
          r[total] = find(e.v);
          ancestor[0][find(e.u)] = ancestor[0][find(e.v)] = total;
          value[total] = e.w;
          p[find(e.u)] = p[find(e.v)] = total;
          total++;
        }
      }
      for (int i = 1; i < log_n; ++i) {
        for (int j = 0; j < (n << 1) - 1; ++j) {
          if (~ancestor[i - 1][j]) {
            ancestor[i][j] = ancestor[i - 1][ancestor[i - 1][j]];
          }
        }
      }
      dfs(n - 1 << 1);
    }

    int go(int x, int limit) {
      for (int i = log_n - 1; ~i; --i) {
        if (~ancestor[i][x] && value[ancestor[i][x]] <= limit) {
          x = ancestor[i][x];
        }
      }
      return x;
    }
  };

  tree_t prefix(n), suffix(n);
  for (int i = 0; i < m; ++i) {
    prefix.edge.emplace_back(x[i], y[i], max(x[i], y[i]));
    suffix.edge.emplace_back(x[i], y[i], -min(x[i], y[i]));
  }
  prefix.init();
  suffix.init();

  vector<pair<int, int>> points;
  fenwick_t<int> fenwick((n << 1) - 1);
  for (int i = 0; i < n; ++i) {
    points.emplace_back(prefix.left[i], suffix.left[i]);
  }
  sort(points.begin(), points.end());

  struct event_t {
    int x, l, r, id, sign;

    event_t(int x = 0, int l = 0, int r = 0, int id = 0, int sign = 0):x(x), l(l), r(r), id(id), sign(sign) {
    }

    bool operator < (const event_t &b) const {
      return x < b.x;
    }
  };

  vector<event_t> events;
  vector<int> answer(q);

  for (int i = 0; i < q; ++i) {
    int x = prefix.go(e[i], r[i]), y = suffix.go(s[i], -l[i]);
    events.emplace_back(prefix.left[x], suffix.left[y], suffix.right[y], i, -1);
    events.emplace_back(prefix.right[x], suffix.left[y], suffix.right[y], i, 1);
  }
  sort(events.begin(), events.end());
  int current = 0;
  for (auto event : events) {
    while (current < n && points[current].first < event.x) {
      fenwick.modify(points[current++].second, 1);
    }
    answer[event.id] += event.sign * (fenwick.query(event.r - 1) - fenwick.query(event.l - 1));
  }
  for (int i = 0; i < q; ++i) {
    if (answer[i]) {
      answer[i] = 1;
    }
  }
  return answer;
}

Compilation message

werewolf.cpp: In member function 'void check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)::tree_t::init()':
werewolf.cpp:102:13: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
       dfs(n - 1 << 1);
           ~~^~~
werewolf.cpp: In instantiation of 'T fenwick_t<T>::query(int) [with T = int]':
werewolf.cpp:155:64:   required from here
werewolf.cpp:26:18: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
       x = (x & x + 1) - 1;
                ~~^~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 368 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 356 KB Output is correct
6 Correct 2 ms 356 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 368 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 356 KB Output is correct
6 Correct 2 ms 356 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 11 ms 1820 KB Output is correct
11 Correct 9 ms 1792 KB Output is correct
12 Correct 8 ms 1792 KB Output is correct
13 Correct 12 ms 1784 KB Output is correct
14 Correct 12 ms 1784 KB Output is correct
15 Correct 13 ms 1920 KB Output is correct

Subtask #3
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1055 ms 111788 KB Output is correct
2 Correct 1484 ms 113260 KB Output is correct
3 Correct 1099 ms 112256 KB Output is correct
4 Correct 1094 ms 111760 KB Output is correct
5 Correct 916 ms 111836 KB Output is correct
6 Correct 1066 ms 111844 KB Output is correct
7 Correct 812 ms 111768 KB Output is correct
8 Correct 1531 ms 113276 KB Output is correct
9 Correct 788 ms 112308 KB Output is correct
10 Correct 516 ms 111848 KB Output is correct
11 Correct 535 ms 111768 KB Output is correct
12 Correct 567 ms 111700 KB Output is correct
13 Correct 1699 ms 113488 KB Output is correct
14 Correct 1883 ms 113336 KB Output is correct
15 Correct 1746 ms 113396 KB Output is correct
16 Correct 1540 ms 113360 KB Output is correct
17 Correct 776 ms 111636 KB Output is correct

Subtask #4
51.0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 368 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 356 KB Output is correct
6 Correct 2 ms 356 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 11 ms 1820 KB Output is correct
11 Correct 9 ms 1792 KB Output is correct
12 Correct 8 ms 1792 KB Output is correct
13 Correct 12 ms 1784 KB Output is correct
14 Correct 12 ms 1784 KB Output is correct
15 Correct 13 ms 1920 KB Output is correct
16 Correct 1055 ms 111788 KB Output is correct
17 Correct 1484 ms 113260 KB Output is correct
18 Correct 1099 ms 112256 KB Output is correct
19 Correct 1094 ms 111760 KB Output is correct
20 Correct 916 ms 111836 KB Output is correct
21 Correct 1066 ms 111844 KB Output is correct
22 Correct 812 ms 111768 KB Output is correct
23 Correct 1531 ms 113276 KB Output is correct
24 Correct 788 ms 112308 KB Output is correct
25 Correct 516 ms 111848 KB Output is correct
26 Correct 535 ms 111768 KB Output is correct
27 Correct 567 ms 111700 KB Output is correct
28 Correct 1699 ms 113488 KB Output is correct
29 Correct 1883 ms 113336 KB Output is correct
30 Correct 1746 ms 113396 KB Output is correct
31 Correct 1540 ms 113360 KB Output is correct
32 Correct 776 ms 111636 KB Output is correct
33 Correct 1496 ms 112196 KB Output is correct
34 Correct 417 ms 50684 KB Output is correct
35 Correct 1739 ms 114236 KB Output is correct
36 Correct 1483 ms 112164 KB Output is correct
37 Correct 1587 ms 113568 KB Output is correct
38 Correct 1376 ms 112720 KB Output is correct
39 Correct 1471 ms 114804 KB Output is correct
40 Correct 1366 ms 126676 KB Output is correct
41 Correct 999 ms 112828 KB Output is correct
42 Correct 633 ms 112176 KB Output is correct
43 Correct 1415 ms 122156 KB Output is correct
44 Correct 1534 ms 113412 KB Output is correct
45 Correct 985 ms 115412 KB Output is correct
46 Correct 1034 ms 115056 KB Output is correct
47 Correct 1647 ms 113632 KB Output is correct
48 Correct 1785 ms 113336 KB Output is correct
49 Correct 1571 ms 113780 KB Output is correct
50 Correct 1422 ms 113460 KB Output is correct
51 Correct 808 ms 126920 KB Output is correct
52 Correct 867 ms 126660 KB Output is correct