Submission #114712

#	Time	Username	Problem	Language	Result	Execution time	Memory
114712		WhipppedCream	Werewolf (IOI18_werewolf)	C++17	15 / 100	1373 ms	524288 KiB

werewolf

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
typedef vector<int> vi;

const int maxn = 4e5+5;

struct dsu
{
	vector<int> par;
	dsu(int n = 0)
	{
		par.resize(n);
		for(int i = 0; i< n; i++) par[i] = i;
	}
	int findset(int x)
	{
		if(x == par[x]) return x;
		return par[x] = findset(par[x]);
	}
};

dsu hum, wolf;

int n, m, q;

vector<int> adj[maxn];

struct tahm
{
	int s, e, l, r, id;
	int hum, wolf;
	tahm(int s, int e, int l, int r, int id): s(s), e(e), l(l), r(r), id(id) {}
};

bool cmpl(tahm a, tahm b)
{
	return a.l< b.l;
}

bool cmpr(tahm a, tahm b)
{
	return a.r< b.r;
}

vector<tahm> kench;
vector<int> twolf[maxn];
vector<int> thum[maxn];

vector<int> pred;
int numb[maxn];
int lb[maxn];
int rb[maxn];

void dfs(int u = 2*n-2)
{
	if(u< n) pred.pb(u);
	for(int v : twolf[u]) dfs(v);
}

void calc(int u = 2*n-2)
{
	lb[u] = 1e9, rb[u] = -1;
	if(u< n) lb[u] = rb[u] = numb[u];
	for(int v : twolf[u])
	{
		calc(v);
		lb[u] = min(lb[u], lb[v]);
		rb[u] = max(rb[u], rb[v]);
	}
	// printf("lb[%d] = %d, rb[%d] = %d\n", u, lb[u], u, rb[u]);
}

struct node
{
	int val;
	node *left, *right;
	node(int _val, node* _left, node *_right)
	{
		val = _val; left = _left; right = _right;
	}
	node* insert(int x, int L = 0, int R = n-1)
	{
		if(L<= x && x<= R)
		{
			if(L == R) return new node(val+1, NULL, NULL);
			int M = (L+R)/2;
			return new node(val+1, left->insert(x, L, M), right->insert(x, M+1, R));
		}
		return this;
	}
	int ask(int i, int j, int L = 0, int R = n-1)
	{
		if(i> R || j< L) return 0;
		if(i<= L && R<= j) return val;
		int M = (L+R)/2;
		int x = left->ask(i, j, L, M);
		int y = right->ask(i, j, M+1, R);
		return x+y;
	}
};


node* zero = new node(0, NULL, NULL);

node* roots[maxn];
vector<int> elems[maxn];

void comb(int u = 2*n-2)
{
	if(u< n)
	{
		elems[u].pb(numb[u]);
		roots[u] = zero->insert(numb[u]);
		return;
	}
	ii big = {0, -1};
	for(int v : thum[u])
	{
		comb(v);
		big = max(big, ii((int) elems[v].size(), v));
	}
	swap(elems[u], elems[big.Y]);
	roots[u] = roots[big.Y];
	for(int v : thum[u])
	{
		for(int x : elems[v])
		{
			elems[u].pb(x);
			roots[u] = roots[u]->insert(x);
		}
	}
}

vector<int> check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) 
{
	n = N;
	m = X.size();
	q = S.size();
	for(int i = 0; i< q; i++) kench.pb(tahm(S[i], E[i], L[i], R[i], i));
	for(int i = 0; i< m; i++)
	{
		adj[X[i]].pb(Y[i]);
		adj[Y[i]].pb(X[i]);
	}
	wolf = dsu(2*n);
	sort(kench.begin(), kench.end(), cmpr);
	int pt = 0;
	int cnt = n;
	for(int i = 0; i< n; i++)
	{
		for(int v : adj[i])
		{
			if(v< i)
			{
				int a = wolf.findset(i);
				int b = wolf.findset(v);
				if(a == b) continue;
				wolf.par[a] = wolf.par[b] = cnt;
				twolf[cnt].pb(a); 
				twolf[cnt].pb(b);
				// printf("%d-->%d %d-->%d\n", cnt, a, cnt, b);
				cnt++;
			}
		}
		while(pt< q && kench[pt].r == i)
		{
			int e = kench[pt].e;
			int pp = wolf.findset(e);
			kench[pt].wolf = pp;
			pt++;
		}
	}
	// printf("finished wolf\n");
	hum = dsu(2*n);
	sort(kench.begin(), kench.end(), cmpl);
	reverse(kench.begin(), kench.end());
	pt = 0;
	cnt = n;
	for(int i = n-1; i>= 0; i--)
	{
		for(int v : adj[i])
		{
			if(v> i)
			{
				int a = hum.findset(v);
				int b = hum.findset(i);
				if(a == b) continue;
				hum.par[a] = hum.par[b] = cnt;
				// printf("%d->%d, %d->%d\n", cnt, a, cnt, b);
				thum[cnt].pb(a); 
				thum[cnt].pb(b);
				cnt++;				
			}
		}
		while(pt< q && kench[pt].l == i)
		{
			int s = kench[pt].s;
			int pp = hum.findset(s);
			kench[pt].hum = pp;
			pt++;
		}
	}

	dfs();
	// for(int i = 0; i< n; i++) printf("%d ", pred[i]);
	// printf("\n");
	for(int i = 0; i< n; i++) numb[pred[i]] = i;
	calc();
	
	// printf("finished renumbering\n");
	
	zero->left = zero->right = zero;
	comb();
	// printf("%d\n", roots[2*n-2]->ask(0, n-1));
	vector<int> ans(q);
	for(int i = 0; i< q; i++)
	{
		int wolf = kench[i].wolf, hum = kench[i].hum;
		int id = kench[i].id;
		int lo = lb[wolf], hi = rb[wolf];
		// if(hum == 5) printf("wolf is %d [%d %d] ans is %d\n", wolf, lo, hi, roots[hum]->ask(0, 0));
		int res = roots[hum]->ask(lo, hi);
		ans[id] = res> 0;
	}
	return ans;
}

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