Submission #548371

#	Time	Username	Problem	Language	Result	Execution time	Memory
548371		cig32	Werewolf (IOI18_werewolf)	C++17	15 / 100	4018 ms	139472 KiB

werewolf

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



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]};
}


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";
      }
    }
  }
  */
  /*
  std::cout << "A array:";
  for(int i=0; i<N; i++) std::cout << " " << A[i];
  std::cout << "\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, humanr, 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: 0 / 34
• Subtask 4: 0 / 51