Submission #1013601

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013601		Malix	Werewolf (IOI18_werewolf)	C++14	49 / 100	659 ms	524288 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> tii;

#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define LSOne(s) ((s)&(-s))

ll INF=1e18+10;
int inf=1e9+10;
ll M=1e9+7;

vi mins,maxs,arr,p;
int n;

void build(int k,int l,int r){
  if(l==r){
    mins[k]=arr[l];
    maxs[k]=arr[l];
    return;
  }
  int m=(l+r)/2;
  build(k*2,l,m);
  build(k*2+1,m+1,r);
  mins[k]=min(mins[k*2],mins[k*2+1]);
  maxs[k]=max(maxs[k*2],maxs[k*2+1]);
}

int minq(int k,int x,int y,int l,int r){
  if(x>y)return inf;
  if(x==l&&r==y)return mins[k];
  int m=(l+r)/2;
  return min(minq(k*2,x,min(y,m),l,m),minq(k*2+1,max(m+1,x),y,m+1,r));
}

int maxq(int k,int x,int y,int l,int r){//cerr<<x<<" "<<y<<"\n";
  if(x>y)return 0;
  if(x==l&&r==y)return maxs[k];
  int m=(l+r)/2;
  return max(maxq(k*2,x,min(y,m),l,m),maxq(k*2+1,max(m+1,x),y,m+1,r));
}

int BS(int l,int r,int x,int y,int u,int v){//cerr<<l<<" "<<r<<"\n";
  int m=(l+r)/2;
  int a=minq(1,u,m,0,n-1);
  int b=maxq(1,m+1,v,0,n-1);
  int c=arr[m];//cerr<<a<<" "<<b<<" "<<c<<"\n";
  if(x<=c&&c<=y&&a>=x&&b<=y)return 1;
  if(l==r)return 0;
  if(a<x&&b>y)return 0;
  if(a>=x&&b<=y){
    if(c<x)return BS(l,m,x,y,u,v);
    else return BS(m+1,r,x,y,u,v);
  }
  if(a<x)return BS(l,m,x,y,u,v);
  return BS(m+1,r,x,y,u,v);
}

int BS2(int l,int r,int x,int y,int u,int v){//cerr<<l<<" "<<r<<"\n";
  int m=(l+r)/2;
  int a=maxq(1,u,m,0,n-1);
  int b=minq(1,m+1,v,0,n-1);
  int c=arr[m];
  swap(a,b);//cerr<<a<<" "<<b<<" "<<c<<"\n";
  if(x<=c&&c<=y&&a>=x&&b<=y)return 1;
  if(l==r)return 0;
  if(a<x&&b>y)return 0;
  if(a>=x&&b<=y){
    if(c<x)return BS2(m+1,r,x,y,u,v);
    else return BS2(l,m,x,y,u,v);
  }
  if(a<x)return BS2(m+1,r,x,y,u,v);
  return BS2(l,m,x,y,u,v);
}

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 Q = S.size();
  if(Q<=3000&&N<=3000&&X.size()<=6000){
    int Q = S.size();
  int m=X.size();
  vii a;
  a.resize(N);
  REP(i,0,m){
    a[X[i]].PB(Y[i]);
    a[Y[i]].PB(X[i]);
  }
  vi ans(Q,0);
  REP(i,0,Q){
    queue<int> pq;
    vi c(N,0),d(N,0);
    pq.push(S[i]);
    while(!pq.empty()){
      int k=pq.front();
      pq.pop();
      if(c[k]||k<L[i])continue;
      c[k]=1;
      for(auto u:a[k])pq.push(u);
    }
    pq.push(E[i]);
    while(!pq.empty()){
      int k=pq.front();
      pq.pop();
      if(d[k]||k>R[i])continue;
      d[k]=1;
      for(auto u:a[k])pq.push(u);
    }
    REP(j,L[i],R[i]+1){
      ans[i]|=(c[j]&d[j]);
    }
  }
  return ans;
  }
  n=N;
  mins.resize(4*N+1);
  maxs.resize(4*N+1);
  int m=X.size();
  vii a;
  a.resize(N);
  REP(i,0,m){
    a[X[i]].PB(Y[i]);
    a[Y[i]].PB(X[i]);
  }
  int k=0;p.resize(N,-1);
  REP(i,0,N)if(a[i].size()==1)k=i;
  arr.PB(k);
  REP(i,0,N-1){
    int c=a[k][0];
    if(arr.size()>=2&&c==arr[arr.size()-2])c=a[k][1];
    arr.PB(c);
    k=c;
  }
  //reverse(arr.begin(),arr.end());
  REP(i,0,N)p[arr[i]]=i;
  build(1,0,n-1);
  vi ans(Q,0);
  REP(i,0,Q){
    if(p[S[i]]<p[E[i]])ans[i]=BS(p[S[i]],p[E[i]],L[i],R[i],p[S[i]],p[E[i]]);
    else ans[i]=BS2(p[E[i]],p[S[i]],L[i],R[i],p[E[i]],p[S[i]]);
  }
  return ans;
}

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