제출 #578437

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
578437		SSRS	늑대인간 (IOI18_werewolf)	C++14	100 / 100	754 ms	129036 KiB

werewolf

#include <bits/stdc++.h>
using namespace std;
const int LOG = 18;
struct unionfind{
  vector<int> p;
  unionfind(int N): p(N, -1){
  }
  int root(int x){
    if (p[x] == -1){
      return x;
    } else {
      p[x] = root(p[x]);
      return p[x];
    }
  }
  bool same(int x, int y){
    return root(x) == root(y);
  }
  void unite(int x, int y){
    x = root(x);
    y = root(y);
    if (x != y){
      p[x] = y;
    }
  }
};
void dfs(vector<vector<int>> &c, vector<int> &L, vector<int> &R, int &t, int v){
  L[v] = t;
  t++;
  for (int w : c[v]){
    dfs(c, L, R, t, w);
  }
  R[v] = t;
}
struct binary_indexed_tree{
  int N;
  vector<int> BIT;
  binary_indexed_tree(int N): N(N), BIT(N + 1, 0){
  }
  void add(int i){
    i++;
    while (i <= N){
      BIT[i]++;
      i += i & -i;
    }
  }
  int sum(int i){
    int ans = 0;
    while (i > 0){
      ans += BIT[i];
      i -= i & -i;
    }
    return ans;
  }
  int sum(int L, int R){
    return sum(R) - sum(L);
  }
};
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();
  int Q = S.size();
  vector<vector<int>> G(N);
  for (int i = 0; i < M; i++){
    G[X[i]].push_back(Y[i]);
    G[Y[i]].push_back(X[i]);
  }
  unionfind UF1(N);
  vector<int> p1(N, -1);
  vector<vector<int>> c1(N);
  for (int i = N - 1; i >= 0; i--){
    for (int j : G[i]){
      if (j > i){
        int x = UF1.root(j);
        if (x != i){
          p1[x] = i;
          c1[i].push_back(x);
          UF1.unite(x, i);
        }
      }
    }
  }
  unionfind UF2(N);
  vector<int> p2(N, -1);
  vector<vector<int>> c2(N);
  for (int i = 0; i < N; i++){
    for (int j : G[i]){
      if (j < i){
        int x = UF2.root(j);
        if (x != i){
          p2[x] = i;
          c2[i].push_back(x);
          UF2.unite(x, i);
        }
      }
    }
  }
  vector<int> L1(N), R1(N);
  int t1 = 0;
  dfs(c1, L1, R1, t1, 0);
  vector<int> L2(N), R2(N);
  int t2 = 0;
  dfs(c2, L2, R2, t2, N - 1);
  vector<vector<int>> pp1(LOG, vector<int>(N, -1));
  pp1[0] = p1;
  for (int i = 0; i < LOG - 1; i++){
    for (int j = 0; j < N; j++){
      if (pp1[i][j] != -1){
        pp1[i + 1][j] = pp1[i][pp1[i][j]];
      }
    }
  }
  vector<vector<int>> pp2(LOG, vector<int>(N, -1));
  pp2[0] = p2;
  for (int i = 0; i < LOG - 1; i++){
    for (int j = 0; j < N; j++){
      if (pp2[i][j] != -1){
        pp2[i + 1][j] = pp2[i][pp2[i][j]];
      }
    }
  }
  vector<int> X1(Q), X2(Q), Y1(Q), Y2(Q);
  for (int i = 0; i < Q; i++){
    int v1 = S[i];
    for (int j = LOG - 1; j >= 0; j--){
      if (pp1[j][v1] >= L[i]){
        v1 = pp1[j][v1];
      }
    }
    X1[i] = L1[v1];
    X2[i] = R1[v1];
    int v2 = E[i];
    for (int j = LOG - 1; j >= 0; j--){
      if (pp2[j][v2] != -1 && pp2[j][v2] <= R[i]){
        v2 = pp2[j][v2];
      }
    }
    Y1[i] = L2[v2];
    Y2[i] = R2[v2];
  }
  vector<vector<int>> query_add(N + 1), query_sub(N + 1);
  for (int i = 0; i < Q; i++){
    query_sub[X1[i]].push_back(i);
    query_add[X2[i]].push_back(i);
  }
  vector<vector<int>> upd(N + 1);
  for (int i = 0; i < N; i++){
    upd[L1[i]].push_back(L2[i]);
  }
  binary_indexed_tree BIT(N);
  vector<int> ans(Q, 0);
  for (int i = 0; i <= N; i++){
    for (int j : query_add[i]){
      ans[j] += BIT.sum(Y1[j], Y2[j]);
    }
    for (int j : query_sub[i]){
      ans[j] -= BIT.sum(Y1[j], Y2[j]);
    }
    for (int j : upd[i]){
      BIT.add(j);
    }
  }
  for (int i = 0; i < Q; i++){
    ans[i] = min(ans[i], 1);
  }
  return ans;
}

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