Submission #249671

#	Time	Username	Problem	Language	Result	Execution time	Memory
249671		quocnguyen1012	Werewolf (IOI18_werewolf)	C++14	100 / 100	896 ms	141592 KiB

werewolf

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ar array

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 4e5 + 5;

int N, M, Q;
int par[maxn], sz[maxn];
vector<int> adj[maxn], tree[maxn];
vector<ar<int, 3>> wolf, people;
int tin[maxn];
int st[maxn], en[maxn];
set<int> node[maxn];
int now[maxn], nsz[maxn];

int finds(int u)
{
  if(par[u] == u) return u;
  return par[u] = finds(par[u]);
}

void merges(int u, int v, bool ok)
{
  u = finds(u); v = finds(v);
  if(u == v) return;
  if(sz[u] < sz[v]) swap(u, v);
  if(!ok) tree[u].eb(v);
  else{
    for(int it : node[v])
      node[u].insert(it);
  }
  par[v] = u;
  sz[u] += sz[v];
}

void dfs(int u)
{
  static int nTime = 0;
  tin[u] = ++nTime;
  for(int v : tree[u]) dfs(v);
}

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> L, std::vector<int> R)
{
  N = _N;
  M = X.size();
  Q = S.size();
  vector<int> res(Q);
  iota(par, par + N, 0);
  fill(sz, sz + N, 1);
  for(int i = 0; i < M; ++i){
    adj[X[i]].eb(Y[i]);
    adj[Y[i]].eb(X[i]);
  }
  for(int i = 0; i < Q; ++i){
    people.pb({L[i], S[i], i});
    wolf.pb({R[i], E[i], i});
  }
  sort(people.rbegin(), people.rend());
  sort(wolf.begin(), wolf.end());
  for(int i = N - 1, ptr = 0; i >= 0; --i){
    for(int e : adj[i]){
      if(e > i){
        merges(e, i, 0);
      }
    }
    while(ptr < Q && people[ptr][0] == i){
      int id = people[ptr][2];
      int u = finds(people[ptr][1]);
      now[id] = u;
      //if(id == 1) cerr << sz[u] << ' ';
      nsz[id] = sz[u];
      ++ptr;
    }
  }
  /*
  for(int i = 0; i < N; ++i){
    for(int j : tree[i]) cerr << j << ' ';
    cerr << '\n';
  }*/
  for(int i = 0; i < N; ++i){
    if(par[i] == i){
      dfs(i);
      break;
    }
  }
  for(int i = 0; i < Q; ++i){
    st[i] = tin[now[i]];
    en[i] = tin[now[i]] + nsz[i] - 1;
    ///cerr << st[i] << ' ' << en[i] << '\n';
  }
  for(int i = 0; i < N; ++i){
    node[i].insert(tin[i]);
  }
  iota(par, par + N, 0);
  fill(sz, sz + N, 1);
  for(int i = 0, ptr = 0; i < N; ++i){
    for(int j : adj[i]) if(j < i) merges(i, j, 1);
    while(ptr < Q && wolf[ptr][0] == i){
      int u = finds(wolf[ptr][1]);
      int id = wolf[ptr][2];
      auto it = node[u].lower_bound(st[id]);
      if(it != node[u].end() && *(it) <= en[id])
        res[id] = true;
      ++ptr;
    }
  }
  return res;
}


#ifdef LOCAL

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #ifdef LOCAL
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  #endif // LOCAL
  int N, M, Q; cin >> N >> M >> Q;
  std::vector<int> X(M), Y(M), S(Q), E(Q), L(Q), R(Q);
  for(auto & it : X) cin >> it;
  for(auto & it : Y) cin >> it;
  for(auto & it : S) cin >> it;
  for(auto & it : E) cin >> it;
  for(auto & it : L) cin >> it;
  for(auto & it : R) cin >> it;

  std::vector<int> A = check_validity(N, X, Y, S, E, L, R);
  for (size_t i = 0; i < A.size(); ++i) {
    printf("%d\n", A[i]);
  }
}
#endif

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