제출 #1280584

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1280584		WH8	늑대인간 (IOI18_werewolf)	C++17	100 / 100	321 ms	85628 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; 
vector<pair<int,int>> ch; 
vector<pair<int,int>> range1, range2;
vector<int> hr, wr, val, ord, botord, fw; 
void upd(int x, int v){
	if(x <= 0)return;
	while(x <= n){
		fw[x]+=v;
		x+=(x&(-x));
	}
}
int qry(int x){
	int res=0;
	while(x > 0){
		res+=fw[x];
		x-=(x&(-x));
	}
	return res;
}

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) {
  n=N, q=s.size(), m=x.size(), newnode=n;
    int max_nodes = n+2*m+100000;            // or n + m + 5 if your build can go that high
    p.assign(max_nodes, -1);
    ch.assign(max_nodes, {-1, -1});
    range1.assign(max_nodes, {INT_MAX, -1});
    range2.assign(max_nodes, {INT_MAX, -1});
    hr.assign(max_nodes, -1);
    wr.assign(max_nodes, -1);
    val.assign(max_nodes, -1);
    ord.assign(max_nodes, -1);
    botord.assign(max_nodes, -1);
    fw.assign(max_nodes, 0);
  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);
  });
  vector<int> qs; for(int i=0;i<q;i++)qs.push_back(i);
  int ptr;
  sort(qs.begin(),qs.end(),[&](auto a, auto b){
	return l[a] > l[b];
  });
  ptr=0;
  int topnode;
  for(auto [a, b] : ed){
	  int pa=par(a), pb=par(b);
	  //~ cout<<pa<<" "<<pb<<endl;
	  if(pa!=pb){
		  int v=min(a, b);
		  while(ptr < q and l[qs[ptr]] > v){
			hr[qs[ptr]]=par(s[qs[ptr]]);
			ptr++;
		  } 
		  //~ 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++;
	  }
  }

  while(ptr < q){
	  hr[qs[ptr]]=par(s[qs[ptr]]);
	  ptr++;
  }
  int nodesreached;
  nodesreached=1;
  auto dfs=[&](auto dfs, int x) -> void {
	  if(ch[x].f==-1){
		  ord[x]=nodesreached;
		  range1[x].f=nodesreached, range1[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);
		  range1[x].f=min(range1[ch[x].f].f, range1[ch[x].s].f);
		  range1[x].s=max(range1[ch[x].s].s, range1[ch[x].f].s);

	  }
	  //~ printf("dfs at %d, range is %d,%d, ch %d,%d\n", x, range1[x].f,range1[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);
  });
  sort(qs.begin(),qs.end(),[&](auto a, auto b){
	return r[a] < r[b];
  });
  ptr=0;
  int bottomnode;
  for(auto [a, b] : ed){
	  int pa=par(a), pb=par(b);
	  if(pa!=pb){
		  int v=max(a, b);
		  while(ptr < q and r[qs[ptr]] < v){
			wr[qs[ptr]]=par(e[qs[ptr]]);
			ptr++;
		  } 

		  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++;
	  }
  }
 
  while(ptr < q){
	wr[qs[ptr]]=par(e[qs[ptr]]);
	ptr++;
  } 

  nodesreached=1;
  auto dfs2=[&](auto dfs2, int x) -> void {
	  if(ch[x].f==-1){
		  botord[ord[x]]=nodesreached;
		  range2[x].f=nodesreached;
		  range2[x].s=nodesreached;
		  //~ printf("dfs2 leaf, ind %d, ord %d, botord  %d\n",x,ord[x],nodesreached);
		  nodesreached++;
	  }
	  else {
		  dfs2(dfs2,ch[x].f);
		  dfs2(dfs2,ch[x].s);
		  range2[x].f=min(range2[ch[x].f].f, range2[ch[x].s].f);
		  range2[x].s=max(range2[ch[x].s].s, range2[ch[x].f].s);
	  }
  };
  dfs2(dfs2, bottomnode);
  //~ for(int i=1;i<=n;i++){
	  //~ assert(botord[i]!=-1);
	  //~ botordtoind[botord[ord[i]]]=i; // this should be a permutation. 
	  //~ cout<<botordtoind[i]<<" ";
  //~ }

  vector<int> ans(q, 0);
  vector<vector<pair<int,int>>> todo(n+1);
  for(int i=0;i<q;i++){
	//~ range[hr[i]].s++; // one index. 
	//~ range[wr[i]].s++;
	todo[range1[hr[i]].f-1].push_back({i, 0}); // (l, r]
	todo[range1[hr[i]].s].push_back({i, 1});
	//~ printf("hr is %d, wr is %d, %d %d , %d %d\n", 
	//~ hr[i], wr[i],range1[hr[i]].f, range1[hr[i]].s, range2[wr[i]].f, range2[wr[i]].s);
  }
  for(int i=1;i<=n;i++){

	upd(botord[i], 1);
	//~ cout<<endl<<i<<" " <<ord[i-1]<<endl;
	for(auto [qind, type] : todo[i]){
		//~ cout<<qind<<" " <<type<<endl;
		int up, down;
		up=qry(range2[wr[qind]].s);
		down=qry(range2[wr[qind]].f-1);
		if(type==0)ans[qind]-=up-down;
		else ans[qind]+=up-down;
		vector<int> p; 

		//~ printf("qind %d, type %d, s %d, f %d, up %d down %d\n",
		//~ qind, type, range2[wr[qind]].s, range2[wr[qind]].f-1, up, down);
	}
  }
  vector<int> A(q);
  //~ for(auto it : st){
	  //~ cout<<it.f << " " <<it.s<<endl;
  //~ }
  for (int i = 0; i < q; ++i) {
	  if(ans[i] > 0)A[i]=1;
	  else A[i]=0;
  }
  return A;
}
/*
5 5 1
0 1
2 4
0 4
3 4
1 3
2 2 2 2

5 5 1
0 1
2 4
0 4
2 3
0 2
3 0 3 3


5 5 1
2 4
0 4
1 4
2 3
0 2
3 0 1 1

6 6 3
0 3 
3 1 
3 4
1 2
2 5
1 5
4 2 1 2
4 2 2 2
5 4 3 4

5 4 1
2 0
0 1 
1 4
4 3 
3 2 1 2 


*/

//~ 1 6 , 2 4
//~ 1 3 , 2 5
//~ 5 6 , 0 5

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