Submission #1182512

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182512		HappyCapybara	Werewolf (IOI18_werewolf)	C++17	0 / 100	484 ms	86024 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;

int cm, cnt;
vector<int> vs, ve, sl, sr, el, er, pp, pm, pl, pr;
vector<vector<int>> g;

int n;
vector<int> w;
vector<vector<int>> st;

void build(int node=1, int tl=0, int tr=n-1){
  if (tl == tr){
    st[node].push_back(w[tl]);
    return;
  }
  int tm = (tl+tr)/2;
  build(node*2, tl, tm);
  build(node*2+1, tm+1, tr);
  for (int x : st[node*2]) st[node].push_back(x);
  for (int x : st[node*2+1]) st[node].push_back(x);
  sort(st[node].begin(), st[node].end());
}

bool isthere(int node, int le, int re){
  int l = 0, r = st[node].size();
  if (r == 0) return false;
  while (l != r-1){
    int m = (l+r)/2;
    if (st[node][m] >= le) r = m;
    else l = m;
  }
  if (r == (int) st[node].size()) return false;
  if (st[node][r] <= re) return true;
  return false;
}

bool query(int ls, int rs, int le, int re, int node=1, int tl=0, int tr=n-1){
  if (ls <= tl && tr <= rs) return isthere(node, le, re);
  int tm = (tl+tr)/2;
  if (ls <= tm && query(ls, rs, le, re, node*2, tl, tm)) return true;
  if (tm+1 <= rs && query(ls, rs, le, re, node*2+1, tm+1, tr)) return true;
  return false;
}

int find(int a){
  if (a == pp[a]) return pp[a];
  return pp[a] = find(pp[a]);
}

void merge(int a, int b, bool sht=false){
  a = find(a);
  b = find(b);
  if (a == b) return;
  pp[b] = a;
  pl[a] = min(pl[a], pl[b]);
  pr[a] = max(pr[a], pr[b]);
  if (sht) return;
  if (pm[a] == -1) g[cm].push_back(-a-1);
  else g[cm].push_back(pm[a]);
  if (pm[b] == -1) g[cm].push_back(-b-1);
  else g[cm].push_back(pm[b]);
  pm[a] = cm;
  cm++;
}

void dfs(int cur, vector<int>& v){
  if (cur < 0){
    v[-cur-1] = cnt;
    cnt++;
    return;
  }
  for (int next : g[cur]) dfs(next, v);
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
  n = N;
  int M = X.size();
  int Q = S.size();
  vector<pair<int,pair<int,int>>> es, ee;
  for (int i=0; i<M; i++){
    es.push_back({min(X[i], Y[i]), {X[i], Y[i]}});
    ee.push_back({max(X[i], Y[i]), {X[i], Y[i]}});
  }
  vector<pair<int,pair<int,int>>> qs, qe;
  for (int i=0; i<Q; i++){
    qs.push_back({L[i], {S[i], i}});
    qe.push_back({R[i], {E[i], i}});
  }
  sort(es.begin(), es.end());
  sort(ee.begin(), ee.end());
  sort(qs.begin(), qs.end());
  sort(qe.begin(), qe.end());
  vs.resize(N);
  ve.resize(N);
  sl.resize(Q);
  sr.resize(Q);
  el.resize(Q);
  er.resize(Q);
  pp.resize(N);
  pm.resize(N);
  pl.resize(N);
  pr.resize(N);

  for (int i=0; i<N; i++){
    pp[i] = i;
    pm[i] = -1;
  }
  g.assign(N-1, vector<int>(0));
  cm = 0;
  for (int i=M-1; i>=0; i--) merge(es[i].second.first, es[i].second.second);
  cnt = 0;
  dfs(N-2, vs);
  for (int i=0; i<N; i++){
    pp[i] = i;
    pl[i] = vs[i];
    pr[i] = vs[i];
  }
  int cur = Q-1;
  for (int i=M-1; i>=0; i--){
    while (cur >= 0 && es[i].first < qs[cur].first){
      sl[qs[cur].second.second] = pl[find(qs[cur].second.first)];
      sr[qs[cur].second.second] = pr[find(qs[cur].second.first)];
      cur--;
    }
    merge(es[i].second.first, es[i].second.second, true);
  }
  while (cur >= 0){
    sl[qs[cur].second.second] = pl[find(qs[cur].second.first)];
    sr[qs[cur].second.second] = pr[find(qs[cur].second.first)];
    cur--;
  }

  for (int i=0; i<N; i++){
    pp[i] = i;
    pm[i] = -1;
  }
  g.assign(N-1, vector<int>(0));
  cm = 0;
  for (int i=0; i<M; i++) merge(ee[i].second.first, ee[i].second.second);
  cnt = 0;
  dfs(N-2, ve);
  for (int i=0; i<N; i++){
    pp[i] = i;
    pl[i] = ve[i];
    pr[i] = ve[i];
  }
  cur = 0;
  for (int i=0; i<M; i++){
    while (cur < Q && ee[i].first > qe[cur].first){
      el[qe[cur].second.second] = pl[find(qe[cur].second.first)];
      er[qe[cur].second.second] = pr[find(qe[cur].second.first)];
      cur++;
    }
    merge(ee[i].second.first, ee[i].second.second, true);
  }
  while (cur < Q){
    el[qe[cur].second.second] = pl[find(qe[cur].second.first)];
    er[qe[cur].second.second] = pr[find(qe[cur].second.first)];
    cur++;
  }

  w.resize(N);
  st.resize(4*N);
  for (int i=0; i<N; i++) w[vs[i]] = ve[i];
  build();

  vector<int> A(Q);
  for (int i=0; i<Q; i++) A[i] = query(sl[i], sr[i], el[i], er[i]);
  return A;
}

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