Submission #538030

#	Time	Username	Problem	Language	Result	Execution time	Memory
538030		8e7	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	440 ms	36568 KiB

long_mansion

//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 500005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
vector<int> pos[maxn];
int c[maxn];
pii ans[maxn];
pii merge(pii x, pii y){return {min(x.ff, y.ff), max(x.ss, y.ss)};}
bool vis[maxn];
struct DSU{
	pii ran[maxn];
	int par[maxn];
	void init(int n) {
		for (int i = 1;i <= n;i++) par[i] = i, ran[i] = {i, i};
	}
	int find(int a) {
		return a == par[a] ? a : (par[a] = find(par[a]));
	}
	pii getran(int a) {
		return ran[find(a)];
	}
	void Union(int a, int b) {
		a = find(a), b = find(b);
		ran[b] = merge(ran[b], ran[a]);
		par[a] = b;
	}
} d;
bool key(int x, pii p) {
	int il = lower_bound(pos[x].begin(), pos[x].end(), p.ff) - pos[x].begin();
	int ir = upper_bound(pos[x].begin(), pos[x].end(), p.ss) - pos[x].begin();
	return ir > il;	
}
int tot;
bool solve(int n, int par) {
	while (true) {
		n = d.find(n);
		pii r = d.getran(n);	
		auto upd = [&] (int x) {
			if (d.find(par) == d.find(x)) return 1;
			if (solve(x, n)) {
				d.Union(x, n);
			} else {
				d.ran[n] = merge(d.ran[n], d.ran[x]);				
			}
			return 0;
		};
		if (r.ff > 1 && key(c[r.ff-1], r)) {
			if (upd(r.ff-1)) return 1;
		} else if (r.ss < tot && key(c[r.ss], r)) {
			if (upd(r.ss+1)) return 1;
		} else {
			break;
		}
	}
	return 0;
}
int main() {
	io
	int n;
	cin >> n;
	tot = n;
	for (int i = 1;i <= n - 1;i++) cin >> c[i];	
	for (int i = 1;i <= n;i++) {
		int bi;
		cin >> bi;
		for (int j = 0;j < bi;j++) {
			int x;cin>> x;
			pos[x].push_back(i);
		}
	}
	d.init(n);
	for (int i = 1;i <= n;i++) {
		if (vis[d.find(i)]) continue;
		solve(i, 0);
		vis[d.find(i)] = 1;
	}
	for (int i = 1;i <= n;i++) {
		ans[i] = d.getran(i);
	}
	int q;
	cin >> q;
	while (q--) {
		int x, y;
		cin >> x >> y;
		cout << (y <= ans[x].ss && y >= ans[x].ff ? "YES" : "NO") << "\n";
	}
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 15 / 15
• Subtask 4: 75 / 75