oj.uz

Submission #686954

# Submission time Handle Problem Language Result Execution time Memory
686954 2023-01-26T04:27:24 Z Ninja_Kunai Werewolf (IOI18_werewolf) C++14
49 / 100
 4000 ms 321412 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 i << 1, l, mid
	#define right i << 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 103552 KB Output is correct
2 Correct 50 ms 103760 KB Output is correct
3 Correct 51 ms 103644 KB Output is correct
4 Correct 52 ms 103624 KB Output is correct
5 Correct 50 ms 103548 KB Output is correct
6 Correct 49 ms 103628 KB Output is correct
7 Correct 50 ms 103584 KB Output is correct
8 Correct 50 ms 103628 KB Output is correct
9 Correct 52 ms 103756 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 103552 KB Output is correct
2 Correct 50 ms 103760 KB Output is correct
3 Correct 51 ms 103644 KB Output is correct
4 Correct 52 ms 103624 KB Output is correct
5 Correct 50 ms 103548 KB Output is correct
6 Correct 49 ms 103628 KB Output is correct
7 Correct 50 ms 103584 KB Output is correct
8 Correct 50 ms 103628 KB Output is correct
9 Correct 52 ms 103756 KB Output is correct
10 Correct 283 ms 104028 KB Output is correct
11 Correct 196 ms 104004 KB Output is correct
12 Correct 65 ms 104152 KB Output is correct
13 Correct 308 ms 104072 KB Output is correct
14 Correct 230 ms 104024 KB Output is correct
15 Correct 304 ms 104308 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 861 ms 157988 KB Output is correct
2 Correct 811 ms 158336 KB Output is correct
3 Correct 841 ms 158328 KB Output is correct
4 Correct 817 ms 158316 KB Output is correct
5 Correct 810 ms 158248 KB Output is correct
6 Correct 829 ms 158324 KB Output is correct
7 Correct 764 ms 158368 KB Output is correct
8 Correct 775 ms 158288 KB Output is correct
9 Correct 347 ms 158272 KB Output is correct
10 Correct 343 ms 158276 KB Output is correct
11 Correct 368 ms 158276 KB Output is correct
12 Correct 386 ms 158312 KB Output is correct
13 Correct 770 ms 158276 KB Output is correct
14 Correct 745 ms 158336 KB Output is correct
15 Correct 781 ms 158260 KB Output is correct
16 Correct 782 ms 158344 KB Output is correct
17 Correct 716 ms 158316 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 103552 KB Output is correct
2 Correct 50 ms 103760 KB Output is correct
3 Correct 51 ms 103644 KB Output is correct
4 Correct 52 ms 103624 KB Output is correct
5 Correct 50 ms 103548 KB Output is correct
6 Correct 49 ms 103628 KB Output is correct
7 Correct 50 ms 103584 KB Output is correct
8 Correct 50 ms 103628 KB Output is correct
9 Correct 52 ms 103756 KB Output is correct
10 Correct 283 ms 104028 KB Output is correct
11 Correct 196 ms 104004 KB Output is correct
12 Correct 65 ms 104152 KB Output is correct
13 Correct 308 ms 104072 KB Output is correct
14 Correct 230 ms 104024 KB Output is correct
15 Correct 304 ms 104308 KB Output is correct
16 Correct 861 ms 157988 KB Output is correct
17 Correct 811 ms 158336 KB Output is correct
18 Correct 841 ms 158328 KB Output is correct
19 Correct 817 ms 158316 KB Output is correct
20 Correct 810 ms 158248 KB Output is correct
21 Correct 829 ms 158324 KB Output is correct
22 Correct 764 ms 158368 KB Output is correct
23 Correct 775 ms 158288 KB Output is correct
24 Correct 347 ms 158272 KB Output is correct
25 Correct 343 ms 158276 KB Output is correct
26 Correct 368 ms 158276 KB Output is correct
27 Correct 386 ms 158312 KB Output is correct
28 Correct 770 ms 158276 KB Output is correct
29 Correct 745 ms 158336 KB Output is correct
30 Correct 781 ms 158260 KB Output is correct
31 Correct 782 ms 158344 KB Output is correct
32 Correct 716 ms 158316 KB Output is correct
33 Correct 3513 ms 318568 KB Output is correct
34 Correct 327 ms 134624 KB Output is correct
35 Correct 3908 ms 321412 KB Output is correct
36 Correct 3178 ms 318432 KB Output is correct
37 Execution timed out 4022 ms 320680 KB Time limit exceeded
38 Halted 0 ms 0 KB -