Submission #1278688

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278688		WH8	Werewolf (IOI18_werewolf)	C++17	15 / 100	499 ms	589824 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;

vector<int> x,y,s,e,l,r,a;
int n,q,m;
int newnode; // for creating nodes. starts at n.  

vector<int> p(200005, -1); // for dsu 
vector<pair<int,int>> ch(600005, {-1, -1}); // for preorder dfs. 
vector<pair<int,int>> range(600005, {1e9, -1}); // node index --> top tree ord range. 
vector<int> val(600005, -1); // store weight of node. 
vector<int> ord(200005, -1); // order in top tree. 
vector<int> botord(200005, -1); // bottom order stored in segment tree. 
vector<int> botordtoind(200005, -1);
int twok[600005][20], twok2[600005][20];
vector<int> dep(600005);

struct node{
	int s, e, m;
	vector<int> v;
	node *l, *r;
	node (int S, int E){
		s=S, e=E, m=(s+e)/2;
		for(int i=S;i<=E;i++){
			v.push_back(botord[i]);
		}
		sort(v.begin(),v.end());
		if(s!=e){
			l=new node(S, m);
			r=new node(m+1, E);
		}
	}
	pair<int,int> qry(int S, int E, int Q){
		if(S <= s and e <= E){
			auto it = lower_bound(v.begin(),v.end(),Q);
			int hi=1e9, lo=-1;
			if(it != v.end())hi=*it;
			if(it != v.begin())lo=*prev(it);
			return {lo, hi};
		}
		else {
			if (E <= m)return l->qry(S,E,Q);
			if (S > m) return r->qry(S,E,Q);
			auto a=l->qry(S, m, Q);
			auto b=r->qry(m+1, E, Q);
			return {max(a.f, b.f), min(a.s, b.s)};
		}
	}
} *root;

int par(int x){
	if(p[x]==-1)return x;
	else return p[x]=par(p[x]);
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y,vector<int> S, vector<int> E,vector<int> L, vector<int> R) {
  swap(n,N);swap(x,X);swap(y,Y);swap(s,S);swap(E,e);swap(l,L);swap(R,r);
  q=s.size(), m=x.size(), newnode=n;
  
  vector<pair<int,int>> ed; 
  for(int i=0;i<m;i++){
	  ed.push_back({x[i], y[i]});
  }
  sort(ed.begin(),ed.end(), [&](auto a, auto b){
	  return min(a.f,a.s) > min(b.f,b.s);
  });
  int topnode=0;
  for(auto [a, b] : ed){
	  int pa=par(a), pb=par(b);
	  //~ cout<<pa<<" "<<pb<<endl;
	  if(pa!=pb){
		  int v=min(a, b);
		  //~ printf("top from %d to %d, par %d to %d, index %d\n", a, b, pa, pb, newnode); 
		  //~ fflush(stdout);
		  val[newnode]=v;
		  topnode=newnode;
		  ch[newnode].f=pa,ch[newnode].s=pb;
		  p[pa]=newnode;
		  p[pb]=newnode;
		  newnode++;
	  }
  }
  int nodesreached;
  nodesreached=0;
  auto dfs=[&](auto dfs, int x) -> void {
	  if(ch[x].f==-1){
		  ord[x]=nodesreached;
		  range[x].f=nodesreached, range[x].s=nodesreached;
		  nodesreached++;
		  
	  }
	  else {
		  dfs(dfs,ch[x].f);
		  dfs(dfs,ch[x].s);
		  //~ assert(range[ch[x].f].s==range[ch[x].s].f-1);
		  range[x].f=min(range[ch[x].f].f, range[ch[x].s].f);
		  range[x].s=max(range[ch[x].s].s, range[ch[x].f].s);
		  twok2[ch[x].f][0]=x;
		  twok2[ch[x].s][0]=x;
	  }
	  //~ printf("dfs at %d, range is %d,%d, ch %d,%d\n", x, range[x].f,range[x].s, ch[x].f, ch[x].s);
  };
  dfs(dfs, topnode);
  
  // now do the bottom tree.
  // reset a bunch of stuff
  for(int i=0;i<n;i++)p[i]=-1;
  
  sort(ed.begin(),ed.end(), [&](auto a, auto b){
	  return max(a.f,a.s) < max(b.f,b.s);
  });
  
  int bottomnode;
  for(auto [a, b] : ed){
	  int pa=par(a), pb=par(b);
	  if(pa!=pb){
		  int v=max(a, b);
		  val[newnode]=v;
		  ch[newnode].f=pa,ch[newnode].s=pb;
		  bottomnode=newnode;
		  p[pa]=newnode;
		  p[pb]=newnode;
		  //~ printf("bot from %d to %d, par %d to %d, index %d\n", a, b, pa, pb, newnode); 
		  //~ fflush(stdout);
		  newnode++;
	  }
  }
  nodesreached=0;
  auto dfs2=[&](auto dfs2, int x) -> void {
	  if(ch[x].f==-1){
		  botord[ord[x]]=nodesreached;
		  botordtoind[nodesreached]=x;
		  //~ printf("dfs2 leaf, ind %d, ord %d, botord %d\n",x,ord[x],nodesreached);
		  nodesreached++;
	  }
	  else {
		  dep[ch[x].f]=dep[x]+1;
		  dep[ch[x].s]=dep[x]+1;
		  dfs2(dfs2,ch[x].f);
		  dfs2(dfs2,ch[x].s);
		  assert(twok[ch[x].f][0]==0 and twok[ch[x].s][0]==0);
		  twok[ch[x].f][0]=x;
		  twok[ch[x].s][0]=x;
	  }
  };
  dfs2(dfs2, bottomnode);
  for(int i=0;i<n;i++){
	  assert(botord[i]!=-1);
	  //~ botordtoind[botord[ord[i]]]=i; // this should be a permutation. 
	  //~ cout<<botordtoind[i]<<" ";
  }
  //~ cout<<endl;
  // initialize twok;
  for(int j=1;j<20;j++){
	  for(int i=0;i<newnode;i++){
		  twok[i][j]=twok[twok[i][j-1]][j-1];
		  twok2[i][j]=twok2[twok2[i][j-1]][j-1];
	  }
  }
  auto kpar = [&](int a, int k) -> int{
	  for(int i=0;i<20;i++){
		  if((1<<i) & k){
			  a=twok[a][i];
		  }
	  }
	  return a;
  };
  auto lca = [&](int a, int b) -> int{
	  if(dep[a] < dep[b])swap(a, b);
	  a=kpar(a, dep[a]-dep[b]);
	  if(a==b)return a;
	  for(int i=19;i>=0;i--){
		  if(twok[a][i]!=twok[b][i]){
			  a=twok[a][i], b=twok[b][i];
		  }
	  }
	  assert(twok[a][0]==twok[b][0]);
	  return twok[a][0];
  };
  root=new node(0, n-1);

  vector<int> A(q);
  //~ for(auto it : st){
	  //~ cout<<it.f << " " <<it.s<<endl;
  //~ }
  for (int i = 0; i < q; ++i) {
	  int cn=s[i];
	  for(int j=19;j>=0;j--){
		  if (twok2[cn][j]!=0 and val[twok2[cn][j]] >= l[i]){
			  cn=twok2[cn][j];
		  }
	  }
	  int sl = botord[ord[e[i]]];
	  pair<int,int> res= root->qry(range[cn].f, range[cn].s, sl);// what if its just one node?
	  //~ printf("cn is %d, ord range %d %d, res %d %d \n", cn, range[cn].f, range[cn].s, res.f, res.s);
	  // res.f largest smaller than sl, res.s smallest larger than sl.  
	  int cand = 1e9;
	  // check both
	  int a;
	  a=res.f;
	  if(a != -1){
		  a=botordtoind[a];
		  int anc=lca(a, e[i]);
		  cand=min(cand, val[anc]);
	  }
	  a=res.s;
	  if(a != 1e9){
		  a=botordtoind[a];
		  //~ printf("lca of end %d and ind %d\n", e[i],a);
		  int anc=lca(a, e[i]);
		  //~ printf("node %d, val %d\n", anc, val[anc]);
		  cand=min(cand, val[anc]);
	  }
	  
	  if(cand <= r[i]){
		  A[i]=1;
	  }
	  else A[i]=0;
  }
  return A;
}

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