Submission #1251885

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251885		meisgood	Werewolf (IOI18_werewolf)	C++20	100 / 100	1059 ms	161560 KiB

werewolf

#include <bits/stdc++.h>
using namespace std ;
#define ll long long
// #define test
#ifndef test
#include "werewolf.h"
#endif
////////////////////////////////////////////////////////////////////////

vector <int> adj1[400003],adj2[400003] ;
int gp1[400003],gp2[400003] ;
int l1[400003],r1[400003] ;
int l2[400003],r2[400003] ;
int w1[400003],w2[400003] ;
int dsu1(int x){
  if (x==gp1[x]) return x ;
  gp1[x]=dsu1(gp1[x]) ;
  return gp1[x] ;
}
int dsu2(int x){
  if (x==gp2[x]) return x ;
  gp2[x]=dsu2(gp2[x]) ;
  return gp2[x] ;
}
int anc1[23][400003] ;
int anc2[23][400003] ;
int Cnt1=1,Cnt2=1 ;
int A[400003],B[400003] ;
void dfs1(int x){
  l1[x]=r1[x]=Cnt1++ ;
  A[l1[x]]=x ;
  for (auto a : adj1[x]){
    dfs1(a) ;
    anc1[0][a]=x ;
    r1[x]=r1[a] ;
  }
}
void dfs2(int x){
  l2[x]=r2[x]=Cnt2++ ;
  B[l2[x]]=x ;
  for (auto a : adj2[x]){
    dfs2(a) ;
    anc2[0][a]=x ;
    r2[x]=r2[a] ;
  }
}
int lift1(int x,int a){
  for (int i = 20 ; i >= 0 ; i --){
    if (w1[anc1[i][x]]<=a) x=anc1[i][x] ;
  }
  return x ;
}
int lift2(int x,int a){
  for (int i = 20 ; i >= 0 ; i --){
    if (w2[anc2[i][x]]>=a) x=anc2[i][x] ;
  }
  return x ;
}
struct SEGT {
  int seg[1600003] ;
  void build(){for (int i = 0 ; i < 1600003 ; i ++) seg[i]=INT_MAX/2 ;}
  void upd(int id,int l,int r,int x,int v){
    if (l==r&&l==x) seg[id]=v ;
    else if (l>x||r<x) ;
    else {
      int md=(l+r)/2 ;
      upd(id*2,l,md,x,v) ;
      upd(id*2+1,md+1,r,x,v) ;
      seg[id]=min(seg[id*2],seg[id*2+1]) ;
    }
  }
  int qq(int id,int l,int r,int ql,int qr){
    if (ql<=l&&r<=qr) return seg[id] ;
    else if (l>qr||r<ql) return INT_MAX/2 ;
    else {
      int md=(l+r)/2 ;
      return min(qq(id*2,l,md,ql,qr),qq(id*2+1,md+1,r,ql,qr)) ;
    }
  }
} sgt ;
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=X.size() ;
  int Q = S.size();
  std::vector<int> AA(Q,0);
  int i,j ;
  for (i = 0 ; i < 400003 ; i ++) gp1[i]=gp2[i]=w1[i]=w2[i]=i ;
  vector <tuple<int,int,int>> ed1,ed2 ;
  for (i = 0 ; i < M ; i ++){
    ed1.push_back({max(X[i],Y[i]),X[i],Y[i]}) ;
    ed2.push_back({min(X[i],Y[i]),X[i],Y[i]}) ;
  }
  sort(ed1.begin(),ed1.end()) ;
  sort(ed2.begin(),ed2.end(),greater<tuple<int,int,int>>()) ;
  int cnt1=N,cnt2=N ;
  for (auto [c,a,b] : ed1){
    a=dsu1(a),b=dsu1(b) ;
    if (a!=b){
      w1[cnt1]=c ;
      adj1[cnt1].push_back(a) ;
      adj1[cnt1].push_back(b) ;
      gp1[a]=cnt1 ;
      gp1[b]=cnt1 ;
      cnt1++ ;
    }
  }
  for (auto [c,a,b] : ed2){
    a=dsu2(a),b=dsu2(b) ;
    if (a!=b){
      w2[cnt2]=c ;
      adj2[cnt2].push_back(a) ;
      adj2[cnt2].push_back(b) ;
      gp2[a]=cnt2 ;
      gp2[b]=cnt2 ;
      cnt2++ ;
    }
  }
  anc1[0][cnt1-1]=cnt1-1 ;
  anc2[0][cnt2-1]=cnt2-1 ;
  dfs1(cnt1-1) ;
  dfs2(cnt2-1) ;
  for (int k = 1 ; k <= 20 ; k ++){
    for (i = 0 ; i < cnt1 ; i ++) anc1[k][i]=anc1[k-1][anc1[k-1][i]] ;
    for (i = 0 ; i < cnt2 ; i ++) anc2[k][i]=anc2[k-1][anc2[k-1][i]] ;
  }
  vector <tuple<int,int,int,int>> qs[400003] ;
  for (i = 0 ; i < Q ; i ++){
    int x1=lift1(E[i],R[i]) ;
    int x2=lift2(S[i],L[i]) ;
    // for (j = l1[x1] ; j <= r1[x1] ; j ++) cout << A[j] << " " ; cout << endl ;
    // for (j = l2[x2] ; j <= r2[x2] ; j ++) cout << B[j] << " " ; cout << endl ;
    qs[l2[x2]].push_back({i,l1[x1],r1[x1],r2[x2]}) ;
  }
  sgt.build() ;
  Cnt1--,Cnt2-- ;
  for (i = 1 ; i <= Cnt2 ; i ++){
    if (B[i]<N) sgt.upd(1,1,Cnt1,l1[B[i]],i) ;
  }
  for (i = 1 ; i <= Cnt2 ; i ++){
    for (auto [id,L1,R1,R2] : qs[i]){
      if (sgt.qq(1,1,Cnt1,L1,R1)<=R2) AA[id]=1 ;
    }
    if (B[i]<N) sgt.upd(1,1,Cnt1,l1[B[i]],INT_MAX/2) ;
  }
  // sort(qs.begin(),qs.end(),comp) ;
  return AA;
}

////////////////////////////////////////////////////////////////////////
#ifdef test
//grader{
#include <cstdio>
#include <cstdlib>
#include <vector>

namespace {

int read_int() {
  int x;
  if (scanf("%d", &x) != 1) {
    fprintf(stderr, "Error while reading input\n");
    exit(1);
  }
  return x;
}

}  // namespace

int main() {
  int N = read_int();
  int M = read_int();
  int Q = read_int();
  std::vector<int> X(M), Y(M), S(Q), E(Q), L(Q), R(Q);
  for (int j = 0; j < M; ++j) {
    X[j] = read_int();
    Y[j] = read_int();
  }
  for (int i = 0; i < Q; ++i) {
    S[i] = read_int();
    E[i] = read_int();
    L[i] = read_int();
    R[i] = read_int();
  }

  std::vector<int> A = check_validity(N, X, Y, S, E, L, R);
  for (size_t i = 0; i < A.size(); ++i) {
    printf("%d\n", A[i]);
  }
  return 0;
}

//grader}
#endif

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