제출 #1035198

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

werewolf

#include "werewolf.h"

#include <bits/stdc++.h>

using namespace std;

struct SegmentTree{
   int n;
   vector<vector<int>> t;
   void init(int _n){
      n=_n;
      t.assign(4*n+1, {});
   }
   void build(int k, int l, int r, const vector<int> &a){
      if (l==r){
         t[k].push_back(a[l]);
         return;
      }
      int mid=(l+r)>>1;
      build(k<<1, l, mid, a);
      build(k<<1|1, mid+1, r, a);
      t[k].resize(t[k<<1].size()+t[k<<1|1].size());
      merge(t[k<<1].begin(), t[k<<1].end(), t[k<<1|1].begin(), t[k<<1|1].end(), t[k].begin());
   }
   bool get(int k, int l, int r, int L, int R, int x, int y){
      if (r<L || R<l) return 0;
      if (L<=l && r<=R){
         return upper_bound(t[k].begin(), t[k].end(), y)!=lower_bound(t[k].begin(), t[k].end(), x);
      }
      int mid=(l+r)>>1;
      return get(k<<1, l, mid, L, R, x, y) || get(k<<1|1, mid+1, r, L, R, x, y);
   }
} st;

const int N=2e5+10, LG=18;

struct DSU{
   int n;
   vector<int> lab;
   vector<int> g[N];
   int tin[N], tout[N], tdfs;
   int up[LG][N];
   void init(int _n, int root){
      n=_n;
      lab.assign(n+1, -1);
      memset(tin, 0, sizeof tin);
      memset(tout, 0, sizeof tout);
      tdfs=-1;
      up[0][root]=root;
   }
   int find_set(int u){
      return lab[u]<0?u:lab[u]=find_set(lab[u]);
   }
   void union_sets(int u, int v){
      v=find_set(v);
      if (v!=u){
         up[0][v]=u;
         g[u].push_back(v);
         lab[u]+=lab[v];
         lab[v]=u;
      }
   }
   void dfs(int u){
      for (int k=1; k<LG; ++k) up[k][u]=up[k-1][up[k-1][u]];
      tin[u]=++tdfs;
      for (int v:g[u]) dfs(v);
      tout[u]=tdfs;
   }
} dsu1, dsu2;

vector<int> g[N];

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();
   for (int i=0; i<M; ++i) g[X[i]].push_back(Y[i]), g[Y[i]].push_back(X[i]);
   int Q=S.size();
   dsu1.init(N, 0);
   for (int i=N-1; i>=0; --i){
      for (int j:g[i]) if (j>i) dsu1.union_sets(i, j);
   }
   dsu2.init(N, N-1);
   for (int i=0; i<N; ++i){
      for (int j:g[i]) if (j<i) dsu2.union_sets(i, j);
   }
   dsu1.dfs(0);
   dsu2.dfs(N-1);
   st.init(N);
   vector<int> a(N);
   for (int i=0; i<N; ++i) a[dsu2.tin[i]]=dsu1.tin[i];
   st.build(1, 0, N-1, a);
   vector<int> ans(Q);
   for (int i=0; i<Q; ++i){
      for (int j=LG-1; j>=0; --j) if (dsu1.up[j][S[i]]>=L[i]) S[i]=dsu1.up[j][S[i]];
      for (int j=LG-1; j>=0; --j) if (dsu2.up[j][E[i]]<=R[i]) E[i]=dsu2.up[j][E[i]];
      ans[i]=st.get(1, 0, N-1, dsu2.tin[E[i]], dsu2.tout[E[i]], dsu1.tin[S[i]], dsu1.tout[S[i]]);
   }
   return ans;
}

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