Submission #1218808

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218808		Malix	Werewolf (IOI18_werewolf)	C++20	0 / 100	4091 ms	43760 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> ti;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
#define all(x) x.begin(),x.end()
 
ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;

vi p,s;
vii a;
vector<pi> q,t;

int parent(int x){
  if(p[x]==x)return x;
  q.PB({x,p[x]});
  return p[x]=parent(p[x]);
}

void merge(int x,int y){
  x=parent(x);
  y=parent(y);
  if(x==y)return;
  if(s[x]<s[y])swap(x,y);
  t.PB({x,s[x]});
  s[x]+=s[y];
  q.PB({y,p[y]});
  p[y]=x;
}

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 = S.size();
  p.resize(n);s.resize(n,1);
  REP(i,0,n)p[i]=i;
  a.resize(n);
  REP(i,0,X.size()){
    a[X[i]].PB(Y[i]);
    a[Y[i]].PB(X[i]);
  }
  vii b(m,vi(5));
  REP(i,0,m)b[i]={L[i],R[i],S[i],E[i],i};
  sort(all(b));
  int k=log2(n)+1,pos=0,loc=k,prev=0;
  vi ans(m,0);
  while(pos<m){
    p.clear();
    p.resize(n);s.resize(n,1);
    REP(i,0,n)p[i]=i;
    vector<pi> arr;
    REP(i,0,prev)for(auto u:a[i]){
      if(u<prev)merge(i,u);
      else arr.PB({u,i});
    }
    sort(all(arr));
    REP(i,loc,n)for(auto u:a[i])if(u>=loc)merge(i,u);
    q.clear();t.clear();
    vii c;
    while(pos<m&&b[pos][0]<loc)c.PB(b[pos++]);
    int sz=c.size(),ps=0;
    REP(i,0,sz)swap(c[i][0],c[i][1]);
    sort(all(c));
    REP(i,0,sz){
      int x=c[i][1],y=c[i][0];
      while(ps<arr.size()&&arr[ps].F<=y){
        merge(arr[ps].F,arr[ps].S);
        ps++;
      }
      q.clear();t.clear();
      if(y>=loc){
        REP(j,x,loc)for(auto u:a[j])merge(j,u);
      }
      else{
        REP(j,x,y+1)for(auto u:a[j])merge(j,u);
        REP(j,y+1,loc)for(auto u:a[j])if(u>=x)merge(j,u);
      }
      REP(j,prev,x)for(auto u:a[j])if(u<=y)merge(i,u);
      if(parent(c[i][2])==parent(c[i][3]))ans[c[i][4]]=1;
      reverse(all(q));reverse(all(t));
      for(auto [u,v]:q)p[u]=v;
      for(auto [u,v]:t)s[u]=v;
    }
    loc=min(loc+k,n);
  }
  return ans;
}

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