Submission #431964

#	Time	Username	Problem	Language	Result	Execution time	Memory
431964		albertolg101	Werewolf (IOI18_werewolf)	C++17	49 / 100	1650 ms	119068 KiB

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"
	
using namespace std;
using pii = pair<int, int>;

struct dsu 
{
	vector<int> parent;
	vector<bool> flag;

	dsu(int n)
	{
		flag.resize(n);

		for(int i = 0 ; i < n ; i++)
			parent.push_back(i);
	}

	int Find (int nod)
	{
		if(parent[nod] == nod)
			return nod;

		return parent[nod] = Find(parent[nod]);
	}

	bool Union (int nod_a, int nod_b, bool sol)
	{
		int x = Find(nod_a),
			y = Find(nod_b);

		if(!flag[x] or !flag[y])
			return false;

		if(!sol)
			parent[min(x, y)] = max(x, y);

		if(sol)
			parent[max(x, y)] = min(x, y);

		return x != y;
	}

	void activate (int x)
	{
		flag[x] = true;
	}
};

vector<int> t;

void update (int x, int xend, int nod, int pos, int val)
{
	if(x == xend)
		return void(t[nod] = val);

	int mid = (x + xend) / 2;
	(pos <= mid ? update(x, mid, nod*2, pos, val) : update(mid+1, xend, nod*2+1, pos, val));
	
	t[nod] = max(t[nod*2], t[nod*2+1]);
}

int query (int x, int xend, int nod, int l, int r)
{
	if(x > r or xend < l)
		return 0;
	
	if(l <= x and xend <= r)
		return t[nod];

	int mid = (x + xend) / 2;
	return max(query(x, mid, nod*2, l, r), query(mid+1, xend, nod*2+1, l, 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 = L.size(), m = X.size();
	vector<vector<int>> g(n);
	
	for(int i = 0 ; i < m ; i++)
	{
		g[X[i]].push_back(Y[i]);
		g[Y[i]].push_back(X[i]);
	}

	dsu dsuL(n), dsuR(n);
	vector<vector<int>> gl(n), gr(n);

	for(int i = 0 ; i < n ; i++)
	{
		int nod = i;
		dsuL.activate(i);
		sort(g[i].rbegin(), g[i].rend());

		for(auto j: g[i])
		{
			int x = dsuL.Find(j);

			if(dsuL.Union(nod, x, false))
			{
				gl[nod].push_back(x);
				gl[x].push_back(nod);
				nod = dsuL.Find(nod);
			}
		}
	}

	for(int i = n - 1 ; i >= 0 ; i--)
	{
		int nod = i;
		dsuR.activate(i);
		reverse(g[i].begin(), g[i].end());

		for(auto j: g[i])
		{
			int x = dsuR.Find(j);

			if(dsuR.Union(nod, x, true))
			{
				gr[nod].push_back(x);
				gr[x].push_back(nod);
				nod = dsuR.Find(nod);
			}
		}
	}

	int cnt = 0;
	vector<int> et, levelL(n), levelR(n);
	vector<pii> indxL(n), indxR(n);
	vector<vector<int>> parentL(n, vector<int> (18)), parentR = parentL;

	function<void(int, int)> dfs1 = [&](int nod, int father)
	{
		indxR[nod].first = et.size();
		et.push_back(nod);

		for(auto i: gl[nod])
		{
			if(i != father)
			{
				levelR[i] = levelR[nod]+1;
				parentR[i][0] = nod;
				dfs1(i, nod);
			}
		}

		indxR[nod].second = et.size() - 1;
	};

	function<void(int, int)> dfs2 = [&](int nod, int father)
	{
		indxL[nod].first = cnt++;
		// cout << nod << ' ' ; 

		for(auto i: gr[nod])
		{
			if(i != father)
			{
				levelL[i] = levelL[nod] + 1;
				parentL[i][0] = nod;
				dfs2(i, nod);
			}
		}

		indxL[nod].second = cnt - 1;
	};

	// cout << endl ;
	dfs1(n-1, -1);
	// for(auto i: et)
	// 	cout << i << ' ' ; 
	// cout << endl ;
	dfs2(0, -1);
	// cout << endl << endl ;

	for(int i = 1 ; i < 18 ; i++)
	{
		for(int nod = 0 ; nod < n ; nod++)
		{
			if((1<<i) <= levelR[nod])
				parentR[nod][i] = parentR[parentR[nod][i-1]][i-1];

			if((1<<i) <= levelL[nod])
				parentL[nod][i] = parentL[parentL[nod][i-1]][i-1];
		}
	}

	vector<pair<pair<int, bool>, int>> v;

	for(int i = 0 ; i < Q ; i++)
	{
		int nod = E[i];

		for(int j = 17 ; j >= 0 ; j--)
		{
			if((1<<j) <= levelR[nod] and parentR[nod][j] <= R[i])
				nod = parentR[nod][j];
		}

		// cout << E[i] << ' ' << R[i] << ' ' << nod << ' ' << indxR[nod].first << ' ' << indxR[nod].second << endl ;

		v.push_back({{indxR[nod].first, false}, i});
		v.push_back({{indxR[nod].second, true}, i});
	}
	// cout << endl ;

	t.resize(6*n);
	sort(v.rbegin(), v.rend());

	cnt = 0;
	vector<int> mm(Q), ans(Q);

	// cout << endl ;
	// for(int i = v.size() - 1 ; i >= 0 ; i--)
	// 	cout << v[i].first.first << ' ' << v[i].first.second << ' ' << v[i].second << endl ;
	// cout << endl ;

	for(int i = 0 ; i < n ; i++)
	{
		while(v.size() and v.back().first.first == i and !v.back().first.second)
		{
			mm[v.back().second] = ++cnt;
			v.pop_back();
		}

		// cout << "u " << et[i] << ' ' << indxL[et[i]].first << ' ' << cnt << endl ;
		update(1, n, 1, indxL[et[i]].first, cnt);

		while(v.size() and v.back().first.first == i and v.back().first.second)
		{
			int nod = S[v.back().second];

			for(int j = 17 ; j >= 0 ; j--)
			{
				if((1<<j) <= levelL[nod] and parentL[nod][j] >= L[v.back().second])
					nod = parentL[nod][j];
			}

			// cout << nod << ' ' << L[v.back().second] << ' ' << indxL[nod].first << ' ' << indxL[nod].second << ' ' << query(1, n, 1, indxL[nod].first, indxL[nod].second) << ' ' << mm[v.back().second] << endl ;

			ans[v.back().second] = (query(1, n, 1, indxL[nod].first, indxL[nod].second) >= mm[v.back().second]);
			v.pop_back();
		}
	}

	return ans;
}

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