Submission #77926

#	Time	Username	Problem	Language	Result	Execution time	Memory
77926		Just_Solve_The_Problem	Werewolf (IOI18_werewolf)	C++11	100 / 100	1269 ms	247460 KiB

werewolf

#include <vector>
#include <memory.h>
#include <algorithm>
#include <numeric>
#include "werewolf.h"
// #include "grader.cpp"
 
#define pb push_back
#define pii pair < int, int >
#define fr first
#define sc second
#define mk make_pair
#define okk puts("OK");
 
using namespace std;
 
const int smallN = (int)6e3 + 7;
const int N = (int)2e5 + 7;
 
int was[smallN];
int used[smallN];
vector < int > gr[N];
int l, r;
int n;
       
void dfs1(int v, int pr) {
	was[v]++;
	used[v] = 1;
	for (int to : gr[v]) {
		if (!used[to] && to >= l) dfs1(to, v);
	}
}
 
void dfs2(int v, int pr) {
	was[v]++;
	used[v] = 1;
	for (int to : gr[v]) {
		if (!used[to] && to <= r) dfs2(to, v);
	}
}  
 
vector < int > subtask12(int &N, vector < int > &X, vector < int > &Y, vector < int > &S, vector < int > &E, vector < int > &L, vector < int > &R) {
	n = N;
	for (int i = 0; i < (int)X.size(); i++) {
		gr[X[i]].pb(Y[i]);
		gr[Y[i]].pb(X[i]);
	}
	vector < int > ans;
	int q = S.size();
	for (int i = 0; i < q; i++) {
		l = L[i];
		r = R[i];
		memset(was, 0, sizeof was);
		dfs1(S[i], S[i]);
		memset(used, 0, sizeof used);
		dfs2(E[i], E[i]);
		memset(used, 0, sizeof used);
		int ok = 1;
		for (int j = l; j <= r; j++) {
			if (was[j] == 2) {
				ans.pb(1);
				ok = 0;
				break;
			}
		}
		if (ok) {
			ans.pb(0);
		}
	}
	return ans;
}
 
struct sparse {
	int table[2][20][N];
	/*
	0 = min
	1 = max
 	*/
 	sparse() { 		
 	}
	int numlog[N];
	void build(vector < int > &a) {
		numlog[0] = numlog[1] = 0;
		int nn = a.size();
		for (int i = 2; i < N; i++) {
			numlog[i] = numlog[i / 2] + 1;
		}
		for (int i = 0; i < 20; i++) {
			for (int j = 0; j < nn; j++) {
				if (i == 0) {
					table[0][i][j] = table[1][i][j] = a[j];
				} else {
					table[0][i][j] = min(table[0][i - 1][j], table[0][i - 1][min(j + (1 << (i - 1)), nn - 1)]);
					table[1][i][j] = max(table[1][i - 1][j], table[1][i - 1][min(j + (1 << (i - 1)), nn - 1)]);
				}
			}
		}
	}
	int getmax(int l, int r) {
		int lg = numlog[r - l + 1];
		return max(table[1][lg][l], table[1][lg][r - (1 << lg) + 1]);
	}
	int getmin(int l, int r) {
		int lg = numlog[r - l + 1];
		return min(table[0][lg][l], table[0][lg][r - (1 << lg) + 1]);
	}
};
 
vector < int > ar;
vector < int > pos;
sparse tb;
 
void dfs3(int v, int pr, int h = 0) {
	ar[h] = v;
	for (int to : gr[v]) {
		if (to != pr) {
			dfs3(to, v, h + 1);
		}
	}
}
 
pii getrange1(int v, int lim) {
	pii ret;
	ret = mk(v, v);
	int lo, hi;
	lo = 1; 
	hi = n + 1;
	while (hi - lo > 1) {
		int md = (lo + hi) >> 1;
		if (tb.getmin(max(0, v - md + 1), v) >= lim) {
			lo = md;
		} else {
			hi = md;
		}
	}
	ret.fr = max(0, v - lo + 1);
	lo = 1;
	hi = n + 1;
	while (hi - lo > 1) {
		int md = (lo + hi) >> 1;
		if (tb.getmin(v, min(v + md - 1, n - 1)) >= lim) {
			lo = md;
		} else {
			hi = md;
		}
	}
	ret.sc = min(v + lo - 1, n - 1);
	return ret;
}
 
pii getrange2(int v, int lim) {
	pii ret;
	ret = mk(v, v);
	int lo, hi;
	lo = 1; 
	hi = n + 1;
	while (hi - lo > 1) {
		int md = (lo + hi) >> 1;
		if (tb.getmax(max(0, v - md + 1), v) <= lim) {
			lo = md;
		} else {
			hi = md;
		}
	}
	ret.fr = max(0, v - lo + 1);
	lo = 1;
	hi = n + 1;
	while (hi - lo > 1) {
		int md = (lo + hi) >> 1;
		if (tb.getmax(v, min(v + md - 1, n - 1)) <= lim) {
			lo = md;
		} else {
			hi = md;
		}
	}
	ret.sc = min(v + lo - 1, n - 1);
	return ret;
}
 
vector < int > subtask3(int &N, vector < int > &X, vector < int > &Y, vector < int > &S, vector < int > &E, vector < int > &L, vector < int > &R) {
	n = N;
	int m = X.size();
	ar.resize(n);
	pos.resize(n);
	vector < int > ans;
	for (int i = 0; i < m; i++) {
		gr[X[i]].pb(Y[i]);
		gr[Y[i]].pb(X[i]);
	}
	for (int i = 0; i < n; i++) {
		if ((int)gr[i].size() == 1) {
			dfs3(i, i);
			break;
		}
	}         
	tb.build(ar);
	for (int i = 0; i < n; i++) {
		pos[ar[i]] = i;
	}
	int q = (int)S.size();
	ans.resize(q);
	for (int i = 0; i < q; i++) {
		int &res = ans[i];
		res = 0;
		pair < int, int > asd1 = getrange1(pos[S[i]], L[i]);
		pair < int, int > asd2 = getrange2(pos[E[i]], R[i]);
		if ((pos[S[i]] <= pos[E[i]] && asd1.sc >= asd2.fr) || (pos[E[i]] <= pos[S[i]] && asd2.sc >= asd1.fr)) {
			res = 1;
		}
	}  
	return ans;
}
 
struct DSU {
	int par[N];
	DSU() {
		iota(par, par + N, 0);
	}
	int getpar(int x) {
		return ((par[x] == x) ? x : par[x] = getpar(par[x]));
	}
};
DSU dsu1, dsu2;
 
struct query {
	int id, t, x;
	query() {
	}
	query(int _id, int _t, int _x) {
		id = _id;
		t = _t;
		x = _x;
	}
};
vector < query > qq;
 
struct fen {
	int tree[N];
	fen() {
		memset(tree, 0, sizeof tree);
	}
	void upd(int pos) {
		while (pos < N) {
			tree[pos]++;
			pos = pos | (pos + 1);
		}
	}
	int get(int r) {
		int res = 0;
		while (r >= 0) {
			res += tree[r];
			r = (r & (r + 1)) - 1;
		}
		return res;
	}
};
fen tr;
 
vector < vector < int > > gr1, gr2;
int par[2][20][N];
int tiktak;
int tin[2][N], tout[2][N];
int pos1[N]; 
 
void dfs(vector < vector < int > > &GR, int id, int v, int pr) {
	par[id][0][v] = pr;
	for (int i = 1; i < 20; i++) {
		par[id][i][v] = par[id][i - 1][par[id][i - 1][v]];
	}
	tin[id][v] = ++tiktak;
	for (int to : GR[v]) {
		dfs(GR, id, to, v);
	}
	tout[id][v] = tiktak;
}
 
vector < int > subtask4(int &N, vector < int > &X, vector < int > &Y, vector < int > &S, vector < int > &E, vector < int > &L, vector < int > &R) {
	n = N;
	dsu1 = DSU();
	dsu2 = DSU();
	int m = X.size();
	int q = S.size();
	vector < int > ans;
	gr1.resize(n);
	gr2.resize(n);
	ans.resize(q);
	for (int i = 0; i < m; i++) {
		gr[X[i]].pb(Y[i]);
		gr[Y[i]].pb(X[i]);
	}                      
	for (int i = n - 1; i >= 0; i--) {
		for (int to : gr[i]) {
			if (i > to) continue;
			int x = dsu1.getpar(i);
			int y = dsu1.getpar(to);
			if (x == y) continue;
			dsu1.par[y] = x;
			gr1[x].pb(y);
		}
	}                       
	for (int i = 0; i < n; i++) {
		for (int to : gr[i]) {
			if (i < to) continue;
			int x = dsu2.getpar(i);
			int y = dsu2.getpar(to);
			if (x == y) continue;
			dsu2.par[y] = x;
			gr2[x].pb(y);
		}
	}                           
	dfs(gr1, 0, dsu1.getpar(0), dsu1.getpar(0));
	tiktak = 0;
	dfs(gr2, 1, dsu2.getpar(0), dsu2.getpar(0));
	for (int i = 0; i < q; i++) {
		int x = S[i];
		int y = E[i];
		int l = L[i];
		int r = R[i];               
		for (int j = 19; j >= 0; j--) { 
			if (par[0][j][x] >= l) x = par[0][j][x];
			if (par[1][j][y] <= r) y = par[1][j][y];
		}
		// cout << i << ' ' << x << ' ' << y << endl;
		qq.pb(query(~i, tin[0][x] - 1, y));
		qq.pb(query(i, tout[0][x], y));
	}
	sort(qq.begin(), qq.end(), [&](query &a, query &b) {
		return a.t < b.t;
	});
	// puts("***");
	for (int i = 0; i < n; i++) {
		pos1[tin[0][i] - 1] = tin[1][i];
	}
	int ord = 0;
	q = (int)qq.size();
	/*for (auto to : qq) {
		cout << to.id << ' ' << to.t << ' ' << to.x << '\n';
	} */
	for (int i = 0; i < q; i++) {
		while (ord < qq[i].t) tr.upd(pos1[ord++]);
		int delta = tr.get(tout[1][qq[i].x]) - tr.get(tin[1][qq[i].x] - 1);
		if (qq[i].id < 0) {
			ans[~qq[i].id] -= delta;
		} else {
			ans[qq[i].id] += delta;
		}
	}
	for (int i = 0; i < (int)ans.size(); i++) {
		ans[i] = (ans[i] > 0);
	}
	return ans;                     
}
 
 
vector < int > check_validity(int N, vector < int > X, vector < int > Y, vector < int > S, vector < int > E, vector < int > L, vector < int > R) {
	return subtask4(N, X, Y, S, E, L, R);
	if (N <= 3000 && (int)X.size() <= 6000 && (int)S.size() <= 3000) {
		return subtask12(N, X, Y, S, E, L, R);
	} else if ((int)X.size() == N - 1) {
		return subtask3(N, X, Y, S, E, L, R);
	} 
	return subtask4(N, X, Y, S, E, L, R);
}

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