Submission #446000

#	Time	Username	Problem	Language	Result	Execution time	Memory
446000		cs71107	Werewolf (IOI18_werewolf)	C++14	100 / 100	884 ms	163372 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;

typedef long long int ll;
typedef pair<int,int> pii;
const int MAXN = 4e5+10;

vector<int> eL[MAXN];
vector<int> eR[MAXN];

vector<pii> queryL[MAXN];
vector<pii> queryR[MAXN];

vector<int> add[MAXN];
vector<pii> query[MAXN];
vector<int> qid[MAXN];

vector<vector<int> > graphL;
vector<vector<int> > graphR;

int Lv[MAXN];
int Rv[MAXN];

int par[MAXN];
int id[MAXN];

int inL[MAXN];
int outL[MAXN];

int inR[MAXN];
int outR[MAXN];

int cal[MAXN];
int tree[MAXN*4];

int seq;

int root(int x){
    if(par[x]==x)return x;
    return par[x] = root(par[x]);
}

void dfsL(int here){

    inL[here] = seq;
    seq++;

    for(int i=0;i<(int)graphL[here].size();i++){
        dfsL(graphL[here][i]);
    }

    outL[here] = seq-1;

    return;
}

void dfsR(int here){

    inR[here] = seq;
    seq++;

    for(int i=0;i<(int)graphR[here].size();i++){
        dfsR(graphR[here][i]);
    }

    outR[here] = seq-1;

    return;
}

inline void update(int tmp){

    while(tmp){
        tree[tmp]++;
        tmp>>=1;
    }
}

inline int getans(int L,int R){

    int res = 0;

    while(L<=R){
        if(L&1){
            res += tree[L];
            L++;
        }
        if(!(R&1)){
            res += tree[R];
            R--;
        }
        L>>=1; R>>=1;
    }

    return res;
}

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) {
  int M = (int)X.size();
  int Q = (int)L.size();

  int x,y;

  for(int i=0;i<M;i++){

    x = X[i];
    y = Y[i];

    if(x>y)swap(x,y);

    eR[x].push_back(y);
    eL[y].push_back(x);

  }

  for(int i=0;i<Q;i++){

    queryL[R[i]].push_back(pii(E[i],i));
    queryR[L[i]].push_back(pii(S[i],i));

  }

  int NN = (N<<1);

  graphL = vector<vector<int> > (NN);
  graphR = vector<vector<int> > (NN);

  int num = N-1;

  for(int i=0;i<N;i++){
    par[i] = i;
    id[i] = i;
  }

  int cur,idx;
  int curid;

  for(int i=0;i<N;i++){

    for(int j=0;j<(int)eL[i].size();j++){
      curid = root(eL[i][j]);

      if(curid^i){
        par[curid] = i;
        num++;
        graphL[num].push_back(id[i]);
        graphL[num].push_back(id[curid]);
        id[i] = num;
      }
    }

    for(int j=0;j<(int)queryL[i].size();j++){
      
      cur = queryL[i][j].f;
      idx = queryL[i][j].s;

      cur = root(cur);

      Lv[idx] = id[cur];
    }
  }

  num = N-1;

  for(int i=0;i<N;i++){
    par[i] = i;
    id[i] = i;
  }

  for(int i=N-1;i>=0;i--){

    for(int j=0;j<(int)eR[i].size();j++){
      curid = root(eR[i][j]);

      if(curid^i){
          par[curid] = i;
          num++;
          graphR[num].push_back(id[i]);
          graphR[num].push_back(id[curid]);
          id[i] = num;
      }
    }

    for(int j=0;j<(int)queryR[i].size();j++){
        cur = queryR[i][j].f;
        idx = queryR[i][j].s;

        cur = root(cur);

        Rv[idx] = id[cur];
    }
  }

  seq = 0;
  dfsL(((N-1)<<1));

  seq = 0;
  dfsR(((N-1)<<1));

  int la,ra,lb,rb;

  for(int i=0;i<Q;i++){

      la = inL[Lv[i]];
      ra = outL[Lv[i]];

      lb = inR[Rv[i]];
      rb = outR[Rv[i]];

      if(la){
          query[la-1].push_back(pii(lb,rb));
          qid[la-1].push_back((i<<1));
      }
      query[ra].push_back(pii(lb,rb));
      qid[ra].push_back((i<<1)|1);
  }

  for(int i=0;i<N;i++){
      add[inL[i]].push_back(inR[i]);
  }

  int base = 1;

  for(;base<NN;base<<=1);

  int sz = 0;

  for(int i=0;i<NN;i++){

      sz = (int)add[i].size();

      for(int j=0;j<sz;j++){
          update(base+add[i][j]);
      }

      sz = (int)query[i].size();

      for(int j=0;j<sz;j++){

          idx = qid[i][j];
          cur = getans(base+query[i][j].f,base+query[i][j].s);


          if(idx&1){
              cal[(idx>>1)]+=cur;
          }
          else {
              cal[(idx>>1)]-=cur;
          }
      }

  }

  vector<int> ans;

  ans = vector<int> (Q);

  for(int i=0;i<Q;i++){
      if(cal[i])ans[i] = 1;
  }

  return ans;
}

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