Submission #101063

#	Time	Username	Problem	Language	Result	Execution time	Memory
101063		Pro_ktmr	Long Mansion (JOI17_long_mansion)	C++14	0 / 100	3034 ms	36212 KiB

long_mansion

#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define PB push_back
#define MP make_pair
#define all(x) x.begin(),x.end()

//Union-Find木(ランク有り)
struct UnionFind{
private:
	vector<int> parent;
	vector<int> rank;
public:
	void init(int N){ //初期化する O(N)
		parent.clear();
		rank.clear();
		for(int i=0; i<N; i++) parent.push_back(i);
		for(int i=0; i<N; i++) rank.push_back(0);
	}
	int root(int a){ //親を返す O(log N)
		if(parent[a] == a) return a;
		return parent[a] = root(parent[a]);
	}
	void unite(int a, int b){ //木を併合する O(log N)
		int rootA = root(a);
		int rootB = root(b);
		if(rootA == rootB) return;
		if(rank[rootA] < rank[rootB]) parent[rootA] = rootB;
		else{
			parent[rootB] = rootA;
			if(rank[rootA] == rank[rootB]) rank[rootA]++;
		}
	}
	bool same(int a, int b){ //属する木が同じかを返す O(log N)
		return root(a) == root(b);
	}
};

int N,locks[500000],Q,X[500000],Y[500000];
vector<int> keys[500000],pos[500000];
UnionFind uf;

bool solving[500000] = {};
pair<int,int> memo[500000];
bool canEnter(int lock, int l, int r){
	if(*lower_bound(pos[lock].begin(), pos[lock].end(), l) <= r) return true;
	else return false;
}
pair<int,pair<int,int>> solve(int now){ //roop,l,r
	if(solving[now]) return MP(now,MP(now,now)); //相互に行き来可能→その2点から行ける範囲は同じ
	if(memo[now] != MP(-1,-1)) return MP(-1, memo[now]);
	if(uf.root(now) != now) return solve(uf.root(now));
	solving[now] = true;

	int l = now; int r = now;
	while(true){
		if(l > 0 && canEnter(locks[l-1], l, r)){
			auto range = solve(l-1);
			l = min(l, range.second.first);
			r = max(r, range.second.second);
			if(range.first >= 0 && range.first != now){
				uf.unite(range.first, now);
				solving[now] = false;
				return MP(range.first, MP(l, r));
			}
			continue;
		}
		if(r+1 < N && canEnter(locks[r], l, r)){
			auto range = solve(r+1);
			l = min(l, range.second.first);
			r = max(r, range.second.second);
			if(range.first >= 0 && range.first != now){
				uf.unite(range.first, now);
				solving[now] = false;
				return MP(range.first, MP(l, r));
			}
			continue;
		}
		break;
	}

	solving[now] = false;
	return MP(-1, memo[now] = MP(l, r));
}

int main(){
	cin >> N;
	for(int i=0; i<N-1; i++){
		cin >> locks[i];
		locks[i]--;
	}
	for(int i=0; i<N; i++){
		int B;
		cin >> B;
		keys[i].resize(B);
		for(int j=0; j<B; j++){
			cin >> keys[i][j];
			keys[i][j]--;
			pos[keys[i][j]].PB(i);
		}
	}
	for(int i=0; i<N; i++) pos[i].PB(INT_MAX);

	//

	uf.init(N);
	for(int i=0; i<N; i++) memo[i] = MP(-1, -1);
	for(int i=0; i<N; i++) solve(i);
	for(int i=0; i<N; i++){
		if(uf.root(i) != i) memo[i] = memo[uf.root(i)];
	}

	//

	cin >> Q;
	for(int i=0; i<Q; i++){
		int X,Y;
		cin >> X >> Y;
		X--; Y--;
		if(memo[X].first <= Y && Y <= memo[X].second) cout << "YES" << endl;
		else cout << "NO" << endl;
	}

	return 0;
}

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