Submission #1029741

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029741		AmirAli_H1	Werewolf (IOI18_werewolf)	C++17	15 / 100	4075 ms	132460 KiB

werewolf

// In the name of Allah

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

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 2e5 + 4;
const int maxs = 4 * maxn;
const int oo = 1e9 + 7;

int n, m, q;
vector<int> adj[maxn], adjx[maxs];
int val1, val2, sz, p[maxs], A[maxs];
vector<pii> Q1[maxs], Q2[maxs];
int R1[maxn], R2[maxn]; vector<int> res;
int st[maxs], ft[maxs], timer = 0;
vector<pii> G1, G2;

int get(int a) {
	return (p[a] == a) ? a : p[a] = get(p[a]);
}

void merge(int a, int b, int x) {
	a = get(a); b = get(b);
	if (a == b) return ;
	int v = sz++; A[v] = x;
	p[v] = v; p[a] = v; p[b] = v;
	adjx[v].pb(a); adjx[v].pb(b);
}

void dfs(int v, bool time) {
	if (time) st[v] = timer++;
	G1.pb(Mp(A[v], v)); G2.pb(Mp(-A[v], v));
	
	for (auto f : Q1[v]) {
		int j = lower_bound(all(G1), Mp(f.F, -oo)) - G1.begin();
		R1[f.S] = G1[j].S;
	}
	for (auto f : Q2[v]) {
		int j = lower_bound(all(G2), Mp(-f.F, -oo)) - G2.begin();
		R2[f.S] = G2[j].S;
	}
	
	for (int u : adjx[v]) {
		dfs(u, time);
	}
	
	G1.pop_back(); G2.pop_back();
	if (time) ft[v] = timer;
}

bool check(int v, int l, int r) {
	if (len(adjx[v]) == 0) {
		return (st[v] >= l && st[v] < r);
	}
	for (int u : adjx[v]) {
		if (check(u, l, r)) return 1;
	}
	return 0;
}

vector<int> check_validity(int Nx, vector<int> ux, vector<int> vx,
								vector<int> sx, vector<int> ex,
								vector<int> lx, vector<int> rx) {
	n = Nx; m = len(ux); q = len(sx);
	for (int i = 0; i < m; i++) {
		int u = ux[i], v = vx[i];
		adj[u].pb(v); adj[v].pb(u);
	}
	
	val1 = 0; sz = val1 + n;
	iota(p + val1, p + sz, val1);
	iota(A + val1, A + sz, 0);
	for (int i = n - 1; i >= 0; i--) {
		for (int j : adj[i]) {
			if (j > i) merge(i + val1, j + val1, i);
		}
	}
	int v1 = sz - 1;
	
	val2 = sz; sz = val2 + n;
	iota(p + val2, p + sz, val2);
	iota(A + val2, A + sz, 0);
	for (int i = 0; i < n; i++) {
		for (int j : adj[i]) {
			if (j < i) merge(i + val2, j + val2, i);
		}
	}
	int v2 = sz - 1;
	
	for (int i = 0; i < q; i++) {
		int s = sx[i], e = ex[i];
		int l = lx[i], r = rx[i];
		Q1[s + val1].pb(Mp(l, i));
		Q2[e + val2].pb(Mp(r, i));
	}
	
	dfs(v1, 1); dfs(v2, 0);
	for (int v = val2; v < val2 + n; v++) st[v] = st[v - val2];
	
	res.resize(q);
	for (int i = 0; i < q; i++) {
		int u1 = R1[i], u2 = R2[i];
		res[i] = check(u2, st[u1], ft[u1]);
	}
	return res;
}

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