Submission #1111615

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111615		epicci23	Werewolf (IOI18_werewolf)	C++17	49 / 100	1451 ms	47200 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 = 1000000007;
vector<int> v[N];
vector<int> Hvis,Wvis,ar,rev;

void create(int c,int p,int ind){
  ar[ind]=c;
  rev[c]=ind;
  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.assign(n+5,0);
  	rev.assign(n+5,0);
    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);
    for(int i=0;i<q;i++){

      int x=S[i],y=E[i],l=L[i],r=R[i];
      x=rev[x],y=rev[y];

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

 vector<int> res(q,0);
 ar.assign(n+5,0);
 rev.assign(n+5,0);

 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);
    for(int i=0;i<q;i++){

      int x,y,l,r;
      cin >> x >> y >> l >> r;

      x=rev[x],y=rev[y];

      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,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,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,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,y,m2)<=r) l2=m2;
          else r2=m2-1;
        } 
        res[i] = (ll <= l2);
        
      }

    }

    for(int i=0;i<q;i++) cout << res[i];
    cout << '\n';
}

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: 34 / 34
• Subtask 4: 0 / 51