제출 #492297

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
492297		Nirjhor	늑대인간 (IOI18_werewolf)	C++17	100 / 100	755 ms	110652 KiB

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"

using namespace std;

const int N = 200010;

pair <int, int> x_range[N], y_range[N];
vector <int> g[N], who[N], adj[N], t[N << 1];
int root[N], p[N], x_in[N], y_in[N], x_out[N], y_out[N], ptr, x_sub[N], y_sub[N];

int find (int x) {
  return root[x] == x ? x : root[x] = find(root[x]);
}

void dfs (int* a, int *b, int u) {
  a[u] = ptr++;
  for (int v : adj[u]) dfs(a, b, v);
  b[u] = ptr;
}

int query (int n, int l, int r, int lo, int hi) {
  for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
    if (l & 1) {
      vector <int> &vec = t[l++];
      int here = lower_bound(vec.begin(), vec.end(), hi) - lower_bound(vec.begin(), vec.end(), lo);
      if (here) return 1;
    }
    if (r & 1) {
      vector <int> &vec = t[--r];
      int here = lower_bound(vec.begin(), vec.end(), hi) - lower_bound(vec.begin(), vec.end(), lo);
      if (here) return 1;
    }
  }
  return 0;
}

vector <int> solve (vector <pair <int, int>> pts, vector <tuple <int, int, int, int>> que) {
  int n = pts.size(), q = que.size();
  sort(pts.begin(), pts.end());
  for (int i = 0; i < n; ++i) t[n + i] = {pts[i].second};
  for (int i = n - 1; i; --i) merge(t[i << 1].begin(), t[i << 1].end(), t[i << 1 | 1].begin(), t[i << 1 | 1].end(), back_inserter(t[i]));
  vector <int> ret;
  for (auto &[l_x, r_x, l_y, r_y] : que) {
    int l = lower_bound(pts.begin(), pts.end(), make_pair(l_x, -1)) - pts.begin();
    int r = lower_bound(pts.begin(), pts.end(), make_pair(r_x, -1)) - pts.begin();
    ret.emplace_back(query(n, l, r, l_y, r_y));
  }
  return ret;
}

vector <int> check_validity (int n, vector <int> ed_x, vector <int> ed_y, vector <int> que_s, vector <int> que_e, vector <int> que_l, vector <int> que_r) {
  int m = ed_x.size(), q = que_s.size();
  for (int i = 0; i < m; ++i) {
    int u = ed_x[i], v = ed_y[i];
    g[u].emplace_back(v);
    g[v].emplace_back(u);
  }

  for (int i = 0; i < q; ++i) {
    who[que_l[i]].emplace_back(i);
  }
  for (int i = 0; i < n; ++i) root[i] = i;
  for (int i = n - 1; i >= 0; --i) {
    set <int> childs;
    for (int j : g[i]) if (j >= i) childs.emplace(find(j));
    for (int j : childs) p[j] = root[j] = i;
    for (int id : who[i]) x_sub[id] = find(que_s[id]);
  }
  for (int i = 1; i < n; ++i) adj[p[i]].emplace_back(i);
  ptr = 0; dfs(x_in, x_out, 0);
  
  for (int i = 0; i < n; ++i) who[i].clear(), adj[i].clear();

  for (int i = 0; i < q; ++i) {
    who[que_r[i]].emplace_back(i);
  }
  for (int i = 0; i < n; ++i) root[i] = i;
  for (int i = 0; i < n; ++i) {
    set <int> childs;
    for (int j : g[i]) if (j <= i) childs.emplace(find(j));
    for (int j : childs) p[j] = root[j] = i;
    for (int id : who[i]) y_sub[id] = find(que_e[id]);
  }
  for (int i = 0; i < n - 1; ++i) adj[p[i]].emplace_back(i);
  ptr = 0; dfs(y_in, y_out, n - 1);

  vector <pair <int, int>> pts(n);
  for (int i = 0; i < n; ++i) pts[i] = make_pair(x_in[i], y_in[i]);
  vector <tuple <int, int, int, int>> que(q);
  for (int i = 0; i < q; ++i) que[i] = make_tuple(x_in[x_sub[i]], x_out[x_sub[i]], y_in[y_sub[i]], y_out[y_sub[i]]);
  return solve(pts, que);
}

컴파일 시 표준 에러 (stderr) 메시지

werewolf.cpp: In function 'std::vector<int> solve(std::vector<std::pair<int, int> >, std::vector<std::tuple<int, int, int, int> >)':
werewolf.cpp:39:23: warning: unused variable 'q' [-Wunused-variable]
   39 |   int n = pts.size(), q = que.size();
      |                       ^

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51