Submission #381188

#	Time	Username	Problem	Language	Result	Execution time	Memory
381188		MatheusLealV	Werewolf (IOI18_werewolf)	C++17	100 / 100	1252 ms	196392 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
using namespace std;
#define N 500050

int n;
int bit[N];
void upd(int x, int v){
	x+=5;
	assert(x>0);
	for(int i = x; i < N; i += (i&-i)) bit[i] += v;
}
int query(int x){
	x+=5;
	assert(x>0);
	int sum = 0;
	for(int i = x; i > 0; i -=(i&-i)) sum += bit[i];
	return sum;
}
struct kruskal_tree{
	vector<int>grafo[N];
	int pai[N], nivel[N], anc[N][20],cnt, v[N];
	int ini[N], fim[N], tempo;
	void init(){
		for(int i=0;i< N;i++)pai[i]=i,nivel[i]=v[i]=0;
		tempo =0;cnt=n;
	}
	int find(int x){
		if(x==pai[x])return x;
		return pai[x]=find(pai[x]);
	}
	void join(int a, int b, int cost){
		a=find(a);b=find(b);
		if(a==b) return;
		++cnt;
		pai[cnt]=cnt;
		grafo[cnt].pb(a);
		grafo[cnt].pb(b);
		pai[a]=cnt;pai[b]=cnt;
		v[cnt] = cost;
	}
	void dfs(int x, int p){
		ini[x]=++tempo;
		nivel[x]=nivel[p]+1;
		anc[x][0]=p;
		for(auto v:grafo[x]){
			if(v==p)continue;
			dfs(v,x);
		}
		fim[x]=tempo;
	}
	void get_anc(){
		memset(anc,-1,sizeof anc);
		for(int i = cnt;i>=1;i--){
			if(!nivel[i]) dfs(i,i);
		}
		for(int j=1;j<20;j++)
			for(int i=1;i<=cnt;i++)
				anc[i][j]=anc[anc[i][j-1]][j-1];
	}
} mn,mx;
struct line{
	int x, yl, yr, id, tipo; //0=ponto,-1 =close, +1 = open
};
vector<line> lines;
vector<int> check_validity(int nn, vector<int> X, vector<int> Y,vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
  n=nn;
  mn.init();mx.init();
  int m = sz(X),q=sz(S);
  vector<array<int,3>> ed[2];
  //criar max mst com arestas = min(a, b)
  //criar min mst com arestas = max(a, b)
  for(int i = 0; i < m;i++){
  	int a = X[i]+1, b = Y[i]+1, c1 = min(a,b),c2=max(a,b);
  	ed[0].pb({c1,a,b});ed[1].pb({c2,a,b});
  }
  sort(all(ed[0]), [&](auto a, auto b){
  	return a[0] > b[0];
  });
  sort(all(ed[1]));
  for(auto w: ed[0]) mx.join(w[1],w[2],w[0]);
  for(auto w: ed[1]) mn.join(w[1],w[2],w[0]);
  mx.get_anc();
  mn.get_anc();
  vector<int> ans(q);
  for(int i =0;i<q; i++){
  	int st = S[i]+1, en = E[i]+1, l = L[i]+1, r = R[i]+1;
  	int u=st,v=en;
  	for(int j = 19; j >= 0; j--)
  		if(mx.anc[u][j] != -1 and mx.v[mx.anc[u][j]] >= l)
  			u = mx.anc[u][j];
  	for(int j = 19; j>=0;j--)
  		if(mn.anc[v][j] != -1 and mn.v[mn.anc[v][j]] <= r)
  			v = mn.anc[v][j];
  	if(st < l or en > r) continue;
  	lines.pb({mn.ini[v], mx.ini[u], mx.fim[u], i, -1});
  	lines.pb({mn.fim[v], mx.ini[u], mx.fim[u], i, 1});
  }
  for(int i = 1; i <= n; i++){
  	lines.pb({mn.ini[i], mx.ini[i], mx.ini[i], i, 0});
  }
  sort(all(lines), [&](auto a, auto b){
  	if(a.x != b.x) return a.x<b.x;
  	return a.tipo < b.tipo;
  });
  for(int i = 0; i < sz(lines); i++){
  	if(lines[i].tipo == -1){
  		ans[lines[i].id] -= query(lines[i].yr);
  		ans[lines[i].id] += query(lines[i].yl - 1);
  	}
  	else if(lines[i].tipo == 1){
  		ans[lines[i].id] += query(lines[i].yr);
  		ans[lines[i].id] -= query(lines[i].yl -1);
  	}
  	else upd(lines[i].yl,1);
  }
  for(int i=0;i<q;i++)ans[i]=min(ans[i],1);
  return ans;
}

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