Submission #92820

#	Time	Username	Problem	Language	Result	Execution time	Memory
92820		psmao	Werewolf (IOI18_werewolf)	C++14	100 / 100	1479 ms	145528 KiB

werewolf

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

#define fo(i,s,t) for(int i = s; i <= t; ++ i)
#define fd(i,s,t) for(int i = s; i >= t; -- i)
#define bf(i,s) for(int i = head[s]; i; i = e[i].next)
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define VI vector<int>
#define sf scanf
#define pf printf
#define fp freopen
#define SZ(x) ((int)(x).size())
#ifdef MPS
#define D(x...) printf(x)
#else
#define D(x...)
#endif
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const int inf = 1<<30;
const ll INF = 1ll<<60;
const db Inf = 1e20;
const db eps = 1e-9;

const int maxn = 200050;

int fa[maxn];
struct KruskalT
{
	VI adj[maxn];
	int tot, anc[maxn][20], in[maxn], out[maxn];
	void link(int u, int v) 
	{
		adj[u].emplace_back(v);
		anc[v][0] = u;
	}
	void init(int N)
	{
		fo(j,1,19) 
			for(int i = 0; i < N; ++ i)
				if(anc[i][j-1] != -1)
					anc[i][j] = anc[anc[i][j-1]][j-1];
	}
	int getsub(int u, int x, int oper) // oper = 0 => >= L[i], 1-> <=R[i]
	{
		if(oper == 0)
		{
			fd(i,19,0) 
				if(anc[u][i] != -1 && anc[u][i] >= x) 
					u = anc[u][i];
			if(u >= x) return u;
			else return -1;
		}
		else
		{
			fd(i,19,0)
				if(anc[u][i] != -1 && anc[u][i] <= x) 
					u = anc[u][i];
			if(u <= x) return u;
			else return -1;
		}
	}
	void dfs(int u)
	{
		in[u] = ++ tot;
		for(auto p : adj[u]) dfs(p);
		out[u] = tot;
	}
}Tu, Tv, T;
int ls[maxn*20], rs[maxn*20], nd[maxn*20], tot;
int rt[maxn], bag[maxn];

int getfa(int x){return fa[x] == x ? x : fa[x] = getfa(fa[x]);}
void add(int &now, int pre, int p, int l, int r)
{
	now = ++ tot;
	nd[now] = nd[pre] + 1; ls[now] = ls[pre]; rs[now] = rs[pre];
	if(l == r) return;
	int mid = l + r >> 1;
	if(p <= mid) add(ls[now], ls[pre], p, l, mid);
	else add(rs[now], rs[pre], p, mid+1, r);
}
int ask(int now, int pre, int l, int r, int L, int R)
{
	if(!now) return 0;
	if(l <= L && R <= r) return nd[now] - nd[pre];
	int mid = L + R >> 1;
	if(r <= mid) return ask(ls[now], ls[pre], l, r, L, mid);
	else if(l > mid) return ask(rs[now], rs[pre], l, r, mid+1, R);
	else return ask(ls[now], ls[pre], l, mid, L, mid) +
				ask(rs[now], rs[pre], mid+1, r, mid+1, R);
}
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(), M = X.size();
  std::vector<int> A(Q);
  // construct two trees
  for(int i = 0; i < N; ++ i) fa[i] = i;
  memset(Tu.anc,0xff,sizeof(Tu.anc));
  memset(Tv.anc,0xff,sizeof(Tv.anc));
  for(int i = 0; i < M; ++ i) T.link(X[i], Y[i]), T.link(Y[i], X[i]);
  for(int i = N-1; i >= 0; -- i)
  {
  	for(auto p : T.adj[i]) if(p > i)
  	{
  		int fx = getfa(p);
  		if(fx != i)	{fa[fx] = i; Tu.link(i, fx); D("%d %d\n",i,fx);}
  	}
  }
  D("~~~~~~~~~~\n");
  for(int i = 0; i < N; ++ i) fa[i] = i;
  for(int i = 0; i < N; ++ i)
  {
  	for(auto p : T.adj[i]) if(p < i)
  	{
  		int fx = getfa(p);
  		if(fx != i) {fa[fx] = i; Tv.link(i, fx); D("%d %d\n",i,fx);}
  	}
  }
  D("~~~~~~~~~\n");
  //build up binary lifting stuffs
  Tu.init(N); Tv.init(N);
  Tu.dfs(0); Tv.dfs(N-1);
  //insert points into persistent rangetree
  for(int i = 0; i < N; ++ i) 
  	bag[Tu.in[i]] = Tv.in[i];
  for(int i = 1; i <= Tu.tot; ++ i) 
  {
  	add(rt[i], rt[i-1], bag[i], 1, Tv.tot);
  	D("%d\n",ask(rt[i],rt[i-1],bag[i],bag[i],1,Tv.tot));
  }
  //now query
  for(int i = 0; i < Q; ++ i)
  {
  	int x = Tu.getsub(S[i], L[i], 0), y = Tv.getsub(E[i], R[i], 1);
  	if(x == -1 || y == -1) {A[i] = 0; continue;}
  	D("%d %d %d\n",i,x,y);
  	D("[%d,%d] [%d,%d]\n",Tu.in[x],Tu.out[x],Tv.in[y],Tv.out[y]);
  	A[i] = ask(rt[Tu.out[x]], rt[Tu.in[x]-1], Tv.in[y], Tv.out[y], 1, Tv.tot);
  	A[i] = (A[i] > 0);
  }
  return A;
}

Compilation message (stderr)

werewolf.cpp: In function 'void add(int&, int, int, int, int)':
werewolf.cpp:85:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
werewolf.cpp: In function 'int ask(int, int, int, int, int, int)':
werewolf.cpp:93:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = L + R >> 1;
            ~~^~~

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