oj.uz

Submission #686879

# Submission time Handle Problem Language Result Execution time Memory
686879 2023-01-26T03:23:26 Z Ninja_Kunai Werewolf (IOI18_werewolf) C++14
49 / 100
 4000 ms 335320 KB 
/**
*    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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 103628 KB Output is correct
2 Correct 50 ms 103640 KB Output is correct
3 Correct 53 ms 103680 KB Output is correct
4 Correct 51 ms 103568 KB Output is correct
5 Correct 53 ms 103564 KB Output is correct
6 Correct 52 ms 103584 KB Output is correct
7 Correct 50 ms 103592 KB Output is correct
8 Correct 50 ms 103676 KB Output is correct
9 Correct 51 ms 103652 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 103628 KB Output is correct
2 Correct 50 ms 103640 KB Output is correct
3 Correct 53 ms 103680 KB Output is correct
4 Correct 51 ms 103568 KB Output is correct
5 Correct 53 ms 103564 KB Output is correct
6 Correct 52 ms 103584 KB Output is correct
7 Correct 50 ms 103592 KB Output is correct
8 Correct 50 ms 103676 KB Output is correct
9 Correct 51 ms 103652 KB Output is correct
10 Correct 296 ms 104272 KB Output is correct
11 Correct 193 ms 104100 KB Output is correct
12 Correct 67 ms 104368 KB Output is correct
13 Correct 321 ms 104164 KB Output is correct
14 Correct 239 ms 104140 KB Output is correct
15 Correct 294 ms 104484 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 853 ms 166592 KB Output is correct
2 Correct 878 ms 166464 KB Output is correct
3 Correct 861 ms 166592 KB Output is correct
4 Correct 936 ms 166652 KB Output is correct
5 Correct 962 ms 166476 KB Output is correct
6 Correct 881 ms 166544 KB Output is correct
7 Correct 737 ms 166484 KB Output is correct
8 Correct 756 ms 166504 KB Output is correct
9 Correct 365 ms 166460 KB Output is correct
10 Correct 403 ms 166484 KB Output is correct
11 Correct 379 ms 166460 KB Output is correct
12 Correct 463 ms 166520 KB Output is correct
13 Correct 811 ms 166628 KB Output is correct
14 Correct 819 ms 166520 KB Output is correct
15 Correct 794 ms 166520 KB Output is correct
16 Correct 757 ms 166600 KB Output is correct
17 Correct 757 ms 166644 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 103628 KB Output is correct
2 Correct 50 ms 103640 KB Output is correct
3 Correct 53 ms 103680 KB Output is correct
4 Correct 51 ms 103568 KB Output is correct
5 Correct 53 ms 103564 KB Output is correct
6 Correct 52 ms 103584 KB Output is correct
7 Correct 50 ms 103592 KB Output is correct
8 Correct 50 ms 103676 KB Output is correct
9 Correct 51 ms 103652 KB Output is correct
10 Correct 296 ms 104272 KB Output is correct
11 Correct 193 ms 104100 KB Output is correct
12 Correct 67 ms 104368 KB Output is correct
13 Correct 321 ms 104164 KB Output is correct
14 Correct 239 ms 104140 KB Output is correct
15 Correct 294 ms 104484 KB Output is correct
16 Correct 853 ms 166592 KB Output is correct
17 Correct 878 ms 166464 KB Output is correct
18 Correct 861 ms 166592 KB Output is correct
19 Correct 936 ms 166652 KB Output is correct
20 Correct 962 ms 166476 KB Output is correct
21 Correct 881 ms 166544 KB Output is correct
22 Correct 737 ms 166484 KB Output is correct
23 Correct 756 ms 166504 KB Output is correct
24 Correct 365 ms 166460 KB Output is correct
25 Correct 403 ms 166484 KB Output is correct
26 Correct 379 ms 166460 KB Output is correct
27 Correct 463 ms 166520 KB Output is correct
28 Correct 811 ms 166628 KB Output is correct
29 Correct 819 ms 166520 KB Output is correct
30 Correct 794 ms 166520 KB Output is correct
31 Correct 757 ms 166600 KB Output is correct
32 Correct 757 ms 166644 KB Output is correct
33 Correct 3384 ms 326788 KB Output is correct
34 Correct 331 ms 145304 KB Output is correct
35 Correct 3780 ms 329512 KB Output is correct
36 Correct 2964 ms 326188 KB Output is correct
37 Correct 3738 ms 328268 KB Output is correct
38 Correct 3611 ms 326860 KB Output is correct
39 Correct 2942 ms 335320 KB Output is correct
40 Correct 2630 ms 334864 KB Output is correct
41 Correct 3452 ms 328020 KB Output is correct
42 Correct 3145 ms 325884 KB Output is correct
43 Correct 3959 ms 333956 KB Output is correct
44 Correct 3819 ms 328448 KB Output is correct
45 Correct 3657 ms 335256 KB Output is correct
46 Execution timed out 4042 ms 335116 KB Time limit exceeded
47 Halted 0 ms 0 KB -