Submission #114734

#	Time	Username	Problem	Language	Result	Execution time	Memory
114734		WhipppedCream	Werewolf (IOI18_werewolf)	C++17	100 / 100	1635 ms	199600 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 = 2e5+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[2*maxn];
vector<int> thum[2*maxn];

vector<int> pred;
int numb[maxn];
int lb[2*maxn];
int rb[2*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]);
}


set<int> roots[2*maxn];
vector<int> elems[2*maxn];
vector<tahm> want[2*maxn];

vector<int> ans;

void comb(int u = 2*n-2)
{
	if(u< n)
	{
		roots[u].insert(numb[u]);
		elems[u].pb(numb[u]);
	}
	ii big = {0, -1};
	for(int v : thum[u])
	{
		comb(v);
		big = max(big, {(int) elems[v].size(), v});
	}
	if(big.Y != -1)
	{
		swap(roots[u], roots[big.Y]);
		swap(elems[u], elems[big.Y]);
		for(int v : thum[u])
		{
			for(int x : elems[v])
			{
				roots[u].insert(x);
				elems[u].pb(x);
			}
		}
	}
	for(tahm kk : want[u])
	{
		int id = kk.id;
		int wolf = kk.wolf;
		int lo = lb[wolf], hi = rb[wolf];
		ans[id] = roots[u].upper_bound(hi) != roots[u].upper_bound(lo-1);
	}
}

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");
	
	ans.resize(q);

	for(int i = 0; i< q; i++)
	{
		int wolf = kench[i].wolf, hum = kench[i].hum;
		want[kench[i].hum].pb(kench[i]);
	}
	comb();
	// printf("%d\n", roots[2*n-2]->ask(0, n-1));
	return ans;
}

Compilation message (stderr)

werewolf.cpp: In function 'std::vector<int> check_validity(int, vi, vi, vi, vi, vi, vi)':
werewolf.cpp:204:7: warning: unused variable 'wolf' [-Wunused-variable]
   int wolf = kench[i].wolf, hum = kench[i].hum;
       ^~~~
werewolf.cpp:204:29: warning: unused variable 'hum' [-Wunused-variable]
   int wolf = kench[i].wolf, hum = kench[i].hum;
                             ^~~

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