제출 #335511

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

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
#define REP(i,n) for(int i=0;i<(n);++i)


struct tree_2d_t {
  vector<pair<int,int> > pts;
  vector<vector<int> > nodes;
  int base;
  int n;

  tree_2d_t(const vector<pair<int,int> >& points) {
    pts = points;
    sort(pts.begin(), pts.end());
    n = pts.size();
    base = 1;
    while (base < n) { base *= 2; }
    nodes.resize(2*base);
    REP(i, n) {
      nodes[base + i].push_back(pts[i].second);
    }
    for (int i = base-1; i >= 1; --i) {
      merge(nodes[2*i].begin(), nodes[2*i].end(),
          nodes[2*i+1].begin(), nodes[2*i+1].end(),
          back_inserter(nodes[i]));
    }
  }

  int query(int x, int yl, int yr) {
    yl = lower_bound(nodes[x].begin(), nodes[x].end(), yl) - nodes[x].begin();
    yr = lower_bound(nodes[x].begin(), nodes[x].end(), yr+1) - nodes[x].begin();
    return yr - yl;
  }

  int query(int xl, int xr, int yl, int yr) {
    // Returns number of points in rectangle [xl, xr) x [yl, yr)
    xl = lower_bound(pts.begin(), pts.end(), make_pair(xl, -1)) - pts.begin();
    xr = lower_bound(pts.begin(), pts.end(), make_pair(xr+1, -1)) - pts.begin();
    int cnt = 0;
    xl += base;
    xr += base-1;
    cnt += query(xl, yl, yr);
    if (xl != xr) {
      cnt += query(xr, yl, yr);
    }
    while (xl/2 != xr/2) {
      if (~xl&1) { cnt += query(xl+1, yl, yr); }
      if (xr&1) { cnt += query(xr-1, yl, yr); }
      xl /= 2;
      xr /= 2;
    }
    return cnt;
  }
};


int fufind(vector<int>& fu, int x) {
  return fu[x] < 0 ? x : fu[x] = fufind(fu, fu[x]);
}

void fujoin(vector<int>& fu, vector<pair<int,int> >& tree, int x, int y) {
  x = fufind(fu, x);
  y = fufind(fu, y);
  if (x != y) {
    int p = fu.size();
    fu[y] = p;
    fu[x] = p;
    fu.push_back(-1);
    tree.push_back(make_pair(y, x));
  }
}


pair<int,int> dfs(vector<pair<int,int> >& tree, int v, int N, int& k) {
  if (v < N) {
    tree[v].first = tree[v].second = k;
    k++;
  } else {
    pair<int,int> A = dfs(tree, tree[v].first, N, k);
    pair<int,int> B = dfs(tree, tree[v].second, N, k);
    tree[v].first = min(A.first, B.first);
    tree[v].second = max(A.second, B.second);
  }
  return make_pair(tree[v].first, tree[v].second);
}


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 Q = S.size();
  vector<int> A(Q);

  // Construct the graph
  vector<vector<int> > adj(N);
  int M = X.size();
  REP(i, M) {
    adj[X[i]].push_back(Y[i]);
    adj[Y[i]].push_back(X[i]);
  }

  // Inits
  vector<int> idx(Q+1);
  vector<int> fu(N);
  vector<pair<int,int> > tree(N);
  vector<int> leads(Q+1);
  vector<pair<int,int> > points(N);
  vector<pair<int,int> > Lrange(Q), Rrange(Q);

  // Sentinels
  L.push_back(0);
  R.push_back(N-1);
  S.push_back(0);
  E.push_back(0);

  REP(i, Q+1) {
    idx[i] = i;
  }

  // Process left
  REP(i, N) {
    fu[i] = -1;
  }
  sort(idx.begin(), idx.end(), [&L](int i, int j) { return L[i] > L[j]; });
  int next = N-1;

  REP(i, Q+1) {
    int limit = L[idx[i]];
    for ( ; next >= limit; next--) {
      // Try to join vertex next
      for (int u : adj[next]) {
        if (u >= limit) {
          fujoin(fu, tree, next, u);
        }
      }
    }
    int lead = fufind(fu, S[idx[i]]);
    leads[idx[i]] = lead;
  }

  int k = 0;
  dfs(tree, tree.size()-1, N, k);

  REP(i, Q) {
    Lrange[i] = tree[leads[i]];
  }
  REP(i, N) {
    points[i].first = tree[i].first;
  }

  // Process right
  REP(i, N) {
    fu[i] = -1;
  }
  fu.resize(N);
  tree.resize(N);
  sort(idx.begin(), idx.end(), [&R](int i, int j) { return R[i] < R[j]; });
  next = 0;

  REP(i, Q+1) {
    int limit = R[idx[i]];
    for ( ; next <= limit; next++) {
      // Try to join vertex next
      for (int u : adj[next]) {
        if (u <= limit) {
          fujoin(fu, tree, next, u);
        }
      }
    }
    int lead = fufind(fu, E[idx[i]]);
    leads[idx[i]] = lead;
  }

  k = 0;
  dfs(tree, tree.size()-1, N, k);

  REP(i, Q) {
    Rrange[i] = tree[leads[i]];
  }
  REP(i, N) {
    points[i].second = tree[i].first;
  }

  tree_2d_t tree_2d(points);

  // Answers
  REP(i, Q) {
    A[i] = tree_2d.query(Lrange[i].first, Lrange[i].second,
        Rrange[i].first, Rrange[i].second) > 0;
  }

  return A;
}

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