Submission #1238382

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238382		noyancanturk	Werewolf (IOI18_werewolf)	C++20	0 / 100	350 ms	31744 KiB

werewolf

#include "werewolf.h"

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

#define pb push_back

using pii=pair<int,int>;

const int lim=2e5+100;

vector<int>v[lim];

int parent[lim],sz[lim],tin[lim];
void init(){
  for(int i=0;i<lim;i++){
    parent[i]=i;
    sz[i]=1;
    tin[i]=INT_MAX;
  }
}

int find(int i){
  if(i==parent[i])return i;
  return find(parent[i]);
}

void merge(int x,int y,int tt){
  x=find(x),y=find(y);
  if(x==y)return;
  if(sz[y]<sz[x])swap(x,y);
  parent[x]=y;
  tin[x]=tt;
  sz[y]+=sz[x];
}

int query(int i,int j){
  int ans=0;
  while(i!=j){
    if(tin[j]<tin[i])swap(i,j);
    ans=max(ans,tin[i]);
    i=parent[i];
  }
  return ans;
}

int N;

void coolmerge(int i,int j){
  vector<pair<int,pii>>todo;
  todo.pb(pair<int,pii>{0,pii{i,j}});
  int x=i,y=j;
  int k=0;
  while(x!=y){
    if(tin[y]<tin[x])swap(x,y);
    int par=parent[x];
    todo.pb(pair<int,pii>{tin[x],pii{x,par}});
    x=par;
  }
  int par=parent[x];
  todo.pb(pair<int,pii>{tin[x],pii{x,par}});
  for(int i=1;i<todo.size();i++){
    int guy=todo[i].second.first,par=todo[i].second.second;
    sz[par]-=sz[guy];
    parent[guy]=guy;
    tin[guy]=INT_MAX;  
  }
  sort(todo.begin(),todo.end());
  for(auto[tt,guys]:todo){
    merge(guys.first,guys.second,tt);
  }
}

vector<int>check_validity(int n,vector<int>X,vector<int>Y,vector<int>s,vector<int>e,vector<int>L,vector<int>R){
  init();
  N=n;
  int m=X.size();
  int q=s.size();
  for(int i=0;i<m;i++){
    v[X[i]].pb(Y[i]);
    v[Y[i]].pb(X[i]);
  }
  for(int i=0;i<n;i++){
    for(int j:v[i]){
      if(j<i){
        merge(i,j,i);
      }
    }
  }
  vector<int>ans(q);
  vector<int>toask[n];
  for(int i=0;i<q;i++){
    toask[L[i]].pb(i);
  }
  for(int i=n-1;0<=i;i--){
    for(int j:v[i]){
      if(i<j){
        coolmerge(i,j);
      }
    }
    for(int id:toask[i]){
      int res=query(s[id],e[id]);
      ans[id]=(res<=R[id]);
    }
  }
  return ans;
}

// 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();
//   std::vector<int> A(Q);
//   for (int i = 0; i < Q; ++i) {
//     A[i] = 0;
//   }
//   return A;
// }

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