제출 #1078266

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

werewolf

#include "werewolf.h"

#include <bits/stdc++.h>

std::vector<int> check_validity(int n, std::vector<int> x, std::vector<int> y, std::vector<int> s, std::vector<int> e, std::vector<int> a, std::vector<int> b) {
  int q = s.size(), m = x.size();
  std::vector<int> pr(n);
  std::function<int(int)> find = [&](int u) {
    return u == pr[u] ? u : pr[u] = find(pr[u]);
  };
  std::vector<std::vector<int>> g(n), tr(n);
  for (int i = 0; i < m; ++i) {
    g[x[i]].push_back(y[i]);
    g[y[i]].push_back(x[i]);
  }
  std::vector<int> ind(n), rank(n);
  std::vector<std::vector<std::array<int, 2>>> at(n);
  auto solve = [&](std::vector<int> &tin, std::vector<int> &tout, std::vector<int> &head) {
    iota(pr.begin(), pr.end(), 0);
    for (int i = 0; i < n; ++i) {
      int u = ind[i];
      for (int j : g[u]) {
        if (rank[j] < i && (j = find(j)) != u) {
          pr[j] = u;
          tr[u].push_back(j);
        }
      }
      for (auto [j, v] : at[u]) {
        head[j] = find(v);
      }
    }
    int timer = 0;
    std::function<void(int)> dfs = [&](int u) {
      tin[u] = ++timer;
      for (int v : tr[u]) {
        dfs(v);
      }
      tout[u] = timer;
    };
    dfs(ind.back());
  };
  std::vector tin(2, std::vector<int>(n)), tout(2, std::vector<int>(n)), head(2, std::vector<int>(q));
  for (int i = 0; i < n; ++i) {
    ind[i] = n - 1 - i;
    rank[n - 1 - i] = i;
  }
  for (int i = 0; i < q; ++i) {
    at[a[i]].push_back({i, s[i]});
  } 
  solve(tin[0], tout[0], head[0]);
  for (int i = 0; i < n; ++i) {
    ind[i] = i;
    rank[i] = i;
    std::vector<int>().swap(tr[i]);
    std::vector<std::array<int, 2>>().swap(at[i]);
  }
  for (int i = 0; i < q; ++i) {
    at[b[i]].push_back({i, e[i]});
  }
  solve(tin[1], tout[1], head[1]);
  std::vector<std::vector<std::array<int, 3>>> queries(n + 1);
  std::vector<int> ft(n + 1);
  for (int i = 0; i < q; ++i) {
    std::array<std::array<int, 2>, 2> range;
    for (int j = 0; j < 2; ++j) {
      range[j] = {tin[j][head[j][i]], tout[j][head[j][i]]};
    }
    queries[range[0][0] - 1].push_back({range[1][0], range[1][1], -i - 1});
    queries[range[0][1]].push_back({range[1][0], range[1][1], i + 1});
  }
  auto upd = [&](int i) {
    for (; i <= n; i += i & -i) {
      ++ft[i];
    }
  };
  auto qry = [&](int i) {
    int cnt = 0;
    for (; i; i -= i & -i) {
      cnt += ft[i];
    }
    return cnt;
  };
  std::vector<int> res(q), pos(n + 1);
  for (int i = 0; i < n; ++i) {
    pos[tin[0][i]] = i;
  }
  for (int i = 1; i <= n; ++i) {
    upd(tin[1][pos[i]]);
    for (auto [l, r, id] : queries[i]) {
      if (id > 0) {
        res[id - 1] += qry(r) - qry(l - 1);
      } else {
        res[-1 - id] -= qry(r) - qry(l - 1); 
      }
    }
  }
  for (int i = 0; i < q; ++i) {
    res[i] = res[i] > 0;
  }
  return res;
}

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