Submission #138719

#	Time	Username	Problem	Language	Result	Execution time	Memory
138719		MAMBA	Werewolf (IOI18_werewolf)	C++17	0 / 100	2494 ms	234972 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

#define rep(i , j ,k) for (int i = j; i < (int)k; i++)
#define pb push_back

typedef vector<int> vi;

const int N = 2e5 + 10;

struct dsu {
	int par[N];
	vi h[N];
	unordered_map<int , int> mp[N];
	dsu() {
		iota(par , par + N, 0);
		rep(i , 0 , N) 
			h[i].pb(i);
	}
	int getPar(int v) {
		return par[v] == v ? v : par[v] = getPar(par[v]);
	}
	bool merge(int u , int v) {
		if ((v = getPar(v)) == (u = getPar(u))) return false;
		if (h[u].size() < h[v].size()) swap(u , v);
		for (auto e : h[v]) {
			mp[u][e] = h[u].size();
			h[u].pb(e);
		}
		par[v] = u;
		return true;
	}		
} dsL , dsR;

int LV[N], RV[N], LS[N] , RS[N];
vi adj[N], lid[N] , rid[N];
map<pair<int , int> , vi> mp1 , mp2;

inline bool Eshterak(int v, int vs , int u , int us) {


	if (us < vs) {
		vi &vec = mp1[{v , u}];
		while ((int)vec.size() < us) {
			int tmp = dsR.h[u][vec.size()];
			int me;
			if (dsL.mp[v].count(tmp))
				me = dsL.mp[v][tmp];
			else 
				me = 1e9;
			if (vec.size()) me = min(me , vec.back());
			vec.pb(me);
		}
		return vec[us - 1] < vs;
	}
	else {
		vi &vec = mp2[{v , u}];
		while ((int)vec.size() < vs) {
			int tmp = dsL.h[v][vec.size()];
			int me;
			if (dsR.mp[u].count(tmp))
				me = dsR.mp[u][tmp];
			else 
				me = 1e9;
			if (vec.size()) me = min(me , vec.back());
			vec.pb(me);
		}

		return vec[vs - 1] < us;
	}
}

vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
	int m = X.size();
	rep(i , 0 , m) {
		adj[X[i]].pb(Y[i]);
		adj[Y[i]].pb(X[i]);
	}
	int q = S.size();
	rep(i , 0 , q) {
		lid[L[i]].pb(i);
		rid[R[i]].pb(i);
	}

	{
		for (int i = N - 1; ~i; i--) {
			for (auto e : adj[i])
				if (e >= i)
					dsL.merge(i , e);
			for (auto e : lid[i]) {
				int u = dsL.getPar(S[e]);
				LV[e] = u;
				LS[e] = dsL.h[u].size();

			}
		}
	}
	{
		for (int i = 0 ; i < N; i++) {
			for (auto e : adj[i])
				if (e <= i)
					dsR.merge(i , e);
			for (auto e : rid[i]) {
				int u = dsR.getPar(E[e]);
				RV[e] = u;
				RS[e] = dsR.h[u].size();

			}
		}
	}


	vi res(q);

	rep(i , 0 , q) 
		if (Eshterak(LV[i] , LS[i] , RV[i] , RS[i]))
			res[i] = 1;

	return res;

}

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