Submission #548376

#	Time	Username	Problem	Language	Result	Execution time	Memory
548376		cig32	Werewolf (IOI18_werewolf)	C++17	100 / 100	1447 ms	221760 KiB

werewolf

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <queue>
#include <iostream>
#include <bits/stdc++.h>
//#include "werewolf.h"

using namespace std;


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);



struct edge {
  int f, t, w;
};
class cmp1 { // MST for wolf
  public:
  bool operator() (edge x, edge y) {
    return x.w > y.w;
  }
};
class cmp2 { // MST for human
  public:
  bool operator() (edge x, edge y) {
    return x.w < y.w;
  }
};

std::priority_queue<edge, std::vector<edge>, cmp1> wolf;
std::priority_queue<edge, std::vector<edge>, cmp2> human;

const int MAXN = 2e5 + 12;
int dsu1[MAXN], dsu2[MAXN];

int set_of1(int u) {
  if(dsu1[u] == u) return u;
  return dsu1[u] = set_of1(dsu1[u]);
}
int set_of2(int u) {
  if(dsu2[u] == u) return u;
  return dsu2[u] = set_of2(dsu2[u]);
}
void union1(int u, int v) {
  dsu1[set_of1(u)] = set_of1(v);
}
void union2(int u, int v) {
  dsu2[set_of2(u)] = set_of2(v);
}

int rep1[MAXN];
int rep2[MAXN];

std::vector<int> krt_wolf[2 * MAXN];
std::vector<int> krt_human[2 * MAXN];

int wlim_wolf[2 * MAXN];
int wlim_human[2 * MAXN];

int assigned[MAXN];
int stoN;
int q;
int mi[2 * MAXN], ma[2 * MAXN];

int par_wolf[19][2 * MAXN];
int wolfdepth[2 * MAXN];
std::pair<int, int> dfs1(int node, int curdepth) {
  wolfdepth[node] = curdepth;
  if(node < stoN) {
    assigned[node] = q++; 
    mi[node] = ma[node] = assigned[node];
    return {assigned[node], assigned[node]};
  }
  mi[node] = 1e9, ma[node] = -1;
  for(int x: krt_wolf[node]) {
    std::pair<int, int> res = dfs1(x, curdepth + 1);
    mi[node] = std::min(mi[node], res.first);
    ma[node] = std::max(ma[node], res.second);
    par_wolf[0][x] = node;
  }
  return {mi[node], ma[node]};
}

int par_human[19][2 * MAXN];

int A[MAXN];
int humandepth[2 * MAXN];

int rangel[2 * MAXN], ranger[2 * MAXN];

std::pair<int, int> dfs2(int node, int curdepth) {
  humandepth[node] = curdepth;
  if(node < stoN) {
    A[q] = assigned[node]; 
    rangel[node] = ranger[node] = q;
    q++;
    return {rangel[node], ranger[node]};
  }
  rangel[node] = 1e9, ranger[node] = -1;
  for(int x: krt_human[node]) {
    std::pair<int, int> res = dfs2(x, curdepth + 1);
    rangel[node] = std::min(rangel[node], res.first);
    ranger[node] = std::max(ranger[node], res.second);
    par_human[0][x] = node;
  }
  return {rangel[node], ranger[node]};
}

struct wavelet_tree {
  int lo, hi;
  wavelet_tree *l, *r;
  int *b, *c, bsz, csz; // c holds the prefix sum of elements
 
  wavelet_tree() {
    lo = 1;
    hi = 0;
    bsz = 0;
    csz = 0, l = NULL;
    r = NULL;
  }
 
  void init(int *from, int *to, int x, int y) {
    lo = x, hi = y;
    if(from >= to) return;
    int mid = (lo + hi) >> 1;
    auto f = [mid](int x) {
      return x <= mid;
    };
    b = (int*)malloc((to - from + 2) * sizeof(int));
    bsz = 0;
    b[bsz++] = 0;
    c = (int*)malloc((to - from + 2) * sizeof(int));
    csz = 0;
    c[csz++] = 0;
    for(auto it = from; it != to; it++) {
      b[bsz] = (b[bsz - 1] + f(*it));
      c[csz] = (c[csz - 1] + (*it));
      bsz++;
      csz++;
    }
    if(hi == lo) return;
    auto pivot = stable_partition(from, to, f);
    l = new wavelet_tree();
    l->init(from, pivot, lo, mid);
    r = new wavelet_tree();
    r->init(pivot, to, mid + 1, hi);
  }
  //kth smallest element in [l, r]
  //for array [1,2,1,3,5] 2nd smallest is 1 and 3rd smallest is 2
  int kth(int l, int r, int k) {
    if(l > r) return 0;
    if(lo == hi) return lo;
    int inLeft = b[r] - b[l - 1], lb = b[l - 1], rb = b[r];
    if(k <= inLeft) return this->l->kth(lb + 1, rb, k);
    return this->r->kth(l - lb, r - rb, k - inLeft);
  }
  //count of numbers in [l, r] Less than or equal to k
  int LTE(int l, int r, int k) {
    if(l > r || k < lo) return 0;
    if(hi <= k) return r - l + 1;
    int lb = b[l - 1], rb = b[r];
    return this->l->LTE(lb + 1, rb, k) + this->r->LTE(l - lb, r - rb, k);
  }
  //count of numbers in [l, r] equal to k
  int count(int l, int r, int k) {
    if(l > r || k < lo || k > hi) return 0;
    if(lo == hi) return r - l + 1;
    int lb = b[l - 1], rb = b[r];
    int mid = (lo + hi) >> 1;
    if(k <= mid) return this->l->count(lb + 1, rb, k);
    return this->r->count(l - lb, r - rb, k);
  }
  //sum of numbers in [l ,r] less than or equal to k
  int sum(int l, int r, int k) {
    if(l > r or k < lo) return 0;
    if(hi <= k) return c[r] - c[l - 1];
    int lb = b[l - 1], rb = b[r];
    return this->l->sum(lb + 1, rb, k) + this->r->sum(l - lb, r - rb, k);
  }
  //count max element in [l, r] stricly smaller than k
  int upper_bound(int l, int r, int k) {
    if(l > r) return -1;
    int uwu = LTE(l, r, k - 1);
    if(uwu == 0) return -1;
    return kth(l, r, uwu);
  }
  ~wavelet_tree() {
    delete l;
    delete r;
  }
};

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) {
  stoN = N;
  for(int i=0; i<N; i++) {
    dsu1[i] = dsu2[i] = i;
    rep1[i] = rep2[i] = i;
    wlim_wolf[i] = wlim_human[i] = i; //idk anymore
  }
  int Q = S.size();
  std::vector<int> Answer(Q);
  int M = X.size();
  for(int i=0; i<M; i++) {
    wolf.push({X[i], Y[i], std::max(X[i], Y[i])});
    human.push({X[i], Y[i], std::min(X[i], Y[i])});
  }
  int newnode = N;
  while(wolf.size()) {
    if(set_of1(wolf.top().f) != set_of1(wolf.top().t)) {
      int ff = rep1[set_of1(wolf.top().f)];
      int tt = rep1[set_of1(wolf.top().t)];
      union1(wolf.top().f, wolf.top().t);
      krt_wolf[newnode].push_back(ff);
      krt_wolf[newnode].push_back(tt);
      wlim_wolf[newnode] = wolf.top().w;
      rep1[set_of1(wolf.top().f)] = newnode;
      newnode++;
    }
    wolf.pop();
  }
  int wolfrt = newnode - 1;
  newnode = N;
  while(human.size()) {
    if(set_of2(human.top().f) != set_of2(human.top().t)) {
      int ff = rep2[set_of2(human.top().f)];
      int tt = rep2[set_of2(human.top().t)];
      union2(human.top().f, human.top().t);
      krt_human[newnode].push_back(ff);
      krt_human[newnode].push_back(tt);
      wlim_human[newnode] = human.top().w;
      rep2[set_of2(human.top().f)] = newnode;
      newnode++;
    }
    human.pop();
  }
  int humanrt = newnode - 1;
  
  
  dfs1(wolfrt, 0);
  par_wolf[0][wolfrt] = wolfrt;
  for(int i=1; i<19; i++) {
    for(int j=0; j<=wolfrt; j++) {
      par_wolf[i][j] = par_wolf[i-1][par_wolf[i-1][j]];
    }
  }
  q = 0;
  dfs2(humanrt, 0);
  par_human[0][humanrt] = humanrt;
  for(int i=1; i<19; i++) {
    for(int j=0; j<=humanrt; j++) {
      par_human[i][j] = par_human[i-1][par_human[i-1][j]];
    }
  }

  /*
  std::cout << "wolf\n";
  for(int i=wolfrt; i >= 0; i--) {
    std::cout << "node "<<i<<". weight limit = "<<wlim_wolf[i]<<", node new ids range = [" << mi[i] << ", " << ma[i] << "]\n";
    for(int x: krt_wolf[i]) std::cout << i << ' ' << x << '\n';
  }
  std::cout << "human\n";
  for(int i=humanrt; i >= 0; i--) {
    std::cout << "node " <<i<<". weight limit = "<<wlim_human[i]<<"\n";
    for(int x: krt_human[i]) std::cout << i << ' ' << x << '\n';
  }

  
  for(int i=0; i<N; i++) {
    for(int j=0; j<N; j++) {
      if(assigned[j] == i) {
        std::cout << "order " << i <<": " << j <<"\n";
      }
    }
  }
  */
  wavelet_tree wlt;
  int B[N + 1];
  for(int i=0; i<N; i++) B[i + 1] = A[i];
  wlt.init(B + 1, B + N + 1, 0, N - 1);
  /*
  std::cout << "A array:";
  for(int i=0; i<N; i++) std::cout << " " << A[i];
  std::cout << "\n"; 
  cout << wlt.LTE(0, 0, 5) << "\n";
  cout << wlt.kth(1, 1, 1) <<"\n";
  cout << wlt.upper_bound(0, 0, 6) << " uss\n";
  */
  for(int i=0; i<Q; i++) {
    for(int j=18; j>=0; j--) {
      if(humandepth[S[i]] >= (1 << j) && wlim_human[par_human[j][S[i]]] >= L[i]) S[i] = par_human[j][S[i]];
      if(wolfdepth[E[i]] >= (1 << j) && wlim_wolf[par_wolf[j][E[i]]] <= R[i]) E[i] = par_wolf[j][E[i]];
    }
    int l = mi[E[i]];
    int r = ma[E[i]];
    int humanl = rangel[S[i]];
    int humanr = ranger[S[i]];
    /*
    std::cout << "query "<<i<<": ";
    std::cout<<S[i]<<" "<<E[i]<<" ";
    std::cout << "human array range [" << humanl << ", " << humanr << "] see see if any element in [" << l << ", " << r << "], ";
    */
    int res = wlt.upper_bound(humanl + 1, humanr + 1, r + 1);
    /*
    int res = -1;
    for(int i = humanl; i <= humanr; i++) {
      if(A[i] <= r) res = std::max(res, A[i]);
    }
    */
    /*
    std::cout << "res=" << res<<"\n";
    */
    if(res != -1 && l <= res && res <= r) {
      Answer[i] = 1;
    }
    else {
      Answer[i] = 0;
    }
    
  }
  return Answer;
}

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