Submission #1111586

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111586		epicci23	Werewolf (IOI18_werewolf)	C++17	15 / 100	1239 ms	35184 KiB

werewolf

#include "bits/stdc++.h"
#include "werewolf.h"
//#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int N = 200005;
const int INF = 1e9;
vector<int> v[N];
vector<int> Hvis,Wvis,ar;

void create(int c,int p,int ind){
  ar[ind]=c;
  for(int x:v[c]){
  	if(x==p) continue;
  	create(x,c,ind+1);
  }
}

void dfs_h(int c,int l){
  if(Hvis[c]) return;
  Hvis[c]=1;
  for(int x:v[c]) if(x>=l) dfs_h(x,l);
}

void dfs_w(int c,int r){
  if(Wvis[c]) return;
  Wvis[c]=1;
  for(int x:v[c]) if(x<=r) dfs_w(x,r);
}

struct SegT{
  vector<int> mn,mx;
  SegT(int _n){
    mn.assign(4*_n+5,INF);
    mx.assign(4*_n+5,-INF);
  }

  void build(int rt,int l,int r){
  	if(l==r){
  	  mn[rt]=mx[rt]=ar[l];
  	  return;
  	}
  	int m=(l+r)/2;
  	build(rt*2,l,m),build(rt*2+1,m+1,r);
  	mn[rt]=min(mn[rt*2],mn[rt*2+1]);
  	mx[rt]=max(mx[rt*2],mx[rt*2+1]);
  }

  int get_max(int rt,int l,int r,int gl,int gr){
   if(l>=gl && r<=gr) return mx[rt];
   if(r<gl || l>gr) return -INF;
   int m=(l+r)/2;
   return max(get_max(rt*2,l,m,gl,gr),get_max(rt*2+1,m+1,r,gl,gr));
  }

  int get_min(int rt,int l,int r,int gl,int gr){
   if(l>=gl && r<=gr) return mn[rt];
   if(r<gl || l>gr) return INF;
   int m=(l+r)/2;
   return min(get_min(rt*2,l,m,gl,gr),get_min(rt*2+1,m+1,r,gl,gr));
  }
};

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 n=_N,m=sz(X),q=sz(L);

  for(int i=0;i<m;i++){
 	int a=X[i],b=Y[i];
 	v[a].push_back(b);
 	v[b].push_back(a);
  }

  vector<int> res(q,0);
  
  if(n<3005){
	   for(int i=0;i<q;i++){
	   int x=S[i],y=E[i],l=L[i],r=R[i];
	   Wvis.assign(n+5,0);
	   Hvis.assign(n+5,0);
	   dfs_h(x,l);
	   dfs_w(y,r);
	   bool ok=0;
	   for(int i=0;i<n;i++) if(Wvis[i] && Hvis[i]) ok=1;
	   res[i]=ok;
	  }
  }
  else{
  	ar.resize(n+5);
    for(int i=0;i<n;i++){
      if(sz(v[i])==1){
        create(i,-1,0);
        break;
      }
    }
    SegT Seg(n+5);
    Seg.build(1,0,n-1);
    for(int i=0;i<q;i++){
      int x=S[i],y=E[i],l=L[i],r=R[i];
      if(x<y){
        int ll = x , rr = n - 1;
        while(ll<rr){
          int mm = (ll+rr+1)/2;
          if(Seg.get_min(1,0,n-1,x,mm)>=l) ll=mm;
          else rr=mm-1;
        }
        int l2 = 0 , r2 = y;
        while(l2<r2){
          int m2 = (l2+r2)/2;
          if(Seg.get_max(1,0,n-1,m2,y)<=r) r2=m2;
          else l2=m2+1;
        } 
        res[i]=(l2<=ll);
      }
      else{
        int ll = 0 , rr = x;
        while(ll<rr){
          int mm = (ll+rr)/2;
          if(Seg.get_min(1,0,n-1,mm,x)>=l) rr=mm;
          else ll=mm+1;
        }

        int l2 = y , r2 = n - 1;
        while(l2<r2){
          int m2 = (l2+r2+1)/2;
          if(Seg.get_max(1,0,n-1,y,m2)<=r) l2=m2;
          else r2=m2-1;
        } 
        res[i]=(ll<=l2);
      }
    }
  }
  return res;
}

/*void _(){
 int n,m,q;
 cin >> n >> m >> q;

 for(int i=0;i<m;i++){
 	int a,b;
 	cin >> a >> b;
 	v[a].push_back(b);
 	v[b].push_back(a);
 }

 while(q--){
  int x,y,l,r;
  cin >> x >> y >> l >> r;
  Wvis.assign(n+5,0);
  Hvis.assign(n+5,0);
  dfs_h(x,l);
  dfs_w(y,r);
  bool ok=0;
  for(int i=0;i<n;i++) if(Wvis[i] && Hvis[i]) ok=1;
  cout << ok;
 }
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}*/

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