제출 #686879

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
686879		Ninja_Kunai	늑대인간 (IOI18_werewolf)	C++14	49 / 100	4042 ms	335320 KiB

werewolf

/**
*    Author :  Nguyen Tuan Vu
*    Created : 25.01.2023
**/

#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define MASK(x) ((1ll)<<(x))
#define BIT(x, i) (((x)>>(i))&(1))
#define ALL(v)  (v).begin(), (v).end()
#define REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define FOR(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define FORD(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i)
#define db(val) "["#val" = "<<(val)<<"] "

template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}

using namespace std;

mt19937 jdg(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r) {return l + jdg() % (r - l + 1);}

const int MAXN = 4e5 + 5;
int n, m, nquery;
pair <int, int> edges[MAXN];
vector <int> adj[MAXN];

struct QUERY {
	int s, t, l, r;
	// constraints : 
	// For each query i : 0 <= i < Q
	// 0 <= l(i) <= s(i) <= n - 1
	// 0 <= e(i) <= r(i) <= n - 1
	// s(i) != e(i)
	// l(i) <= r(i)

	QUERY() {}
	QUERY(int s, int t, int l, int r) {
		this->s = s;
		this->t = t;
		this->l = l;
		this->r = r;
	}
} q[MAXN];

namespace sub2 {
	int dd[2][MAXN], cur;

	void dfs(int type, int u, int i) {
		if (dd[type][u] == cur) return;
		//cout << u << ' ' << trans << '\n';
		dd[type][u] = cur;

		for (auto v : adj[u]) {
			if (type == 0 && v >= q[i].l) {
				dfs(type, v, i);
			}

			if (type == 1 && v <= q[i].r) {
				dfs(type, v, i);
			}
		}
	}

	vector <int> solve() {
		vector <int> tmp;
		FOR(i, 1, nquery) {
			++cur;
			dfs(0, q[i].s, i);
			dfs(1, q[i].t, i);
			bool ok = 0;
			REP(j, n) if (dd[0][j] == cur && dd[1][j] == cur) {
				ok = 1;
				break;
			}

			if (ok) tmp.push_back(1);
			else tmp.push_back(0);
		}

		return tmp;
	}
};

namespace sub3 {
	bool check() {
		if (m != n - 1) return false;
		int cnt2 = 0, cnt1 = 0;

		REP(i, n) {
			if (adj[i].size() != 1 && adj[i].size() != 2) return false;
			if (adj[i].size() == 2) cnt2++;
			else cnt1++;
		}

		return (cnt1 == 2 && cnt2 == n - 2);
	}

	int pos[MAXN], a[MAXN], pMin[MAXN][20], pMax[MAXN][20];
	vector <int> solve() {
		int root = 0, pre = -1;
		REP(i, n) if (adj[i].size() == 1) {
			root = i;
			break;
		}

		n = 0;
		while (1) {
			a[++n] = root;
			bool ok = 0;

			for (auto x : adj[root]) if (x == pre) {
				continue;
			}
			else {
				pre = root;
				root = x;
				ok = 1;
				break;
			}

			if (ok == 0) break;
		}

		//cout << n << '\n';
		//FOR(i, 1, n) cout << a[i] << " \n"[i == n];
		auto log2 = [&] (int x) {
			return 31 - __builtin_clz(x);
		};

		FOR(i, 1, n) {
			pos[a[i]] = i;
			pMin[i][0] = pMax[i][0] = a[i];
		}

		FOR(i, 1, log2(n)) FOR(j, 1, n - MASK(i) + 1) {
			pMin[j][i] = min(pMin[j][i - 1], pMin[j + MASK(i - 1)][i - 1]);
			pMax[j][i] = max(pMax[j][i - 1], pMax[j + MASK(i - 1)][i - 1]);
		}

		auto getMin = [&] (int l, int r) {
			int k = log2(r - l + 1);
			return min(pMin[l][k], pMin[r - MASK(k) + 1][k]);
		};

		auto getMax = [&] (int l, int r) {
			int k = log2(r - l + 1);
			return max(pMax[l][k], pMax[r - MASK(k) + 1][k]);
		};

		vector <int> tmp;
		FOR(i, 1, nquery) {
			//cout << q[i].s << ' ' << q[i].t << ' ';
			//cout << pos[q[i].s] << ' ' << pos[q[i].t] << '\n';
			if (pos[q[i].s] < pos[q[i].t]) {
				//cout << "*";
				int l = pos[q[i].s] - 1, r = pos[q[i].t] + 1;
				while (r - l > 1) {
					int mid = (l + r) >> 1;
					if (getMin(pos[q[i].s], mid) >= q[i].l) l = mid;
					else r = mid;
				}

				int L = pos[q[i].s] - 1, R = pos[q[i].t] + 1;
				while (R - L > 1) {
					int mid = (L + R) >> 1;
					if (getMax(mid, pos[q[i].t]) <= q[i].r) R = mid;
					else L = mid;
				}

				if (R <= l) tmp.push_back(1);
				else tmp.push_back(0);
			}
			else {
				int l = pos[q[i].t] - 1, r = pos[q[i].s] + 1;
				while (r - l > 1) {
					int mid = (l + r) >> 1;
					if (getMax(pos[q[i].t], mid) <= q[i].r) l = mid;
					else r = mid;
				}

				int L = pos[q[i].t] - 1, R = pos[q[i].s] + 1;
				while (R - L > 1) {
					int mid = (L + R) >> 1;
					if (getMin(mid, pos[q[i].s]) >= q[i].l) R = mid;
					else L = mid;
				}

				if (R <= l) tmp.push_back(1);
				else tmp.push_back(0);				
			}
		}

		return tmp;
	}
};

namespace sub4 {
	vector <int> line[MAXN], adj2[MAXN];
	int par[MAXN], tin[2][MAXN], tout[2][MAXN], cnt;
	set <int> it[MAXN << 2];

	void dfs(int u, int type) {
		tin[type][u] = ++cnt;
		for (auto v : adj2[u]) {
			dfs(v, type);
		}

		tout[type][u] = cnt;
	}

	#define left mid << 1, l, mid
	#define right mid << 1 | 1, mid + 1, r
	int get_root(int u) {return (par[u] < 0 ? u : par[u] = get_root(par[u]));}
	void update(int u, int val, int i = 1, int l = 1, int r = n) {
		if (l > u || r < u) return;
		it[i].insert(val);
		if (l == r) return;
		int mid = (l + r) >> 1;
		update(u, val, left);
		update(u, val, right);
	}

	bool check(int u, int v, int borderL, int borderR, int i = 1, int l = 1, int r = n) {
		if (l > v || r < u) return 0;
		if (u <= l && r <= v) {
			auto jt = it[i].lower_bound(borderL);
			if (jt == it[i].end()) return 0;
			return (*jt <= borderR);
		}

		int mid = (l + r) >> 1;
		bool L = check(u, v, borderL, borderR, left);
		bool R = check(u, v, borderL, borderR, right);
		return L | R;
	}

	vector <int> solve() {
		FOR(i, 1, nquery) line[q[i].l].push_back(i);
		memset(par, -1, sizeof par);
		FORD(u, n - 1, 0) {
			for (auto v : adj[u]) if (v > u) {
				v = get_root(v);
				if (v != u) {
					par[v] = u;
					adj2[u].push_back(v);
				}
			}

			for (auto i : line[u]) {
				q[i].s = get_root(q[i].s);
			}
		}

		//REP(i, n) {
			//for (auto v : adj2[i]) cout << v << ' ';
			//cout << '\n';
		//}
		dfs(0, 0);
		//REP(i, n) cout << tin[0][i] << " \n"[i == n - 1];
		//cout << "*";
		//return vector <int> (n, 0);
		memset(par, -1, sizeof par);
		FOR(i, 0, n - 1) line[i].clear(), adj2[i].clear();
		FOR(i, 1, nquery) line[q[i].r].push_back(i);
		FOR(u, 0, n - 1) {
			for (auto v : adj[u]) if (v < u) {
				v = get_root(v);
				if (v != u) {
					par[v] = u;
					adj2[u].push_back(v);
				}
			}

			for (auto i : line[u]) {
				q[i].t = get_root(q[i].t);
			}
		}

		cnt = 0;
		dfs(n - 1, 1);
		REP(i, n) update(tin[0][i], tin[1][i]);
		vector <int> tmp;
		FOR(i, 1, nquery) {
			tmp.push_back(check(tin[0][q[i].s], tout[0][q[i].s], tin[1][q[i].t], tout[1][q[i].t]));
		}

		return tmp;
	}
};

vector <int> check_validity(int N, vector <int> X, vector <int> Y, vector <int> S, vector <int> T, vector <int> L, vector <int> R) {
	n = N; m = X.size(); nquery = S.size();
	REP(i, m) {
		edges[i + 1] = make_pair(X[i], Y[i]);
		adj[X[i]].push_back(Y[i]);
		adj[Y[i]].push_back(X[i]);
	}

	REP(i, nquery) q[i + 1] = QUERY(S[i], T[i], L[i], R[i]);

	if (n <= 3000 && m <= 6000 && nquery <= 3000) return sub2::solve();
	else if (sub3::check()) return sub3::solve();
	else return sub4::solve();
	return vector <int> (nquery, 0);
}

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