Submission #170529

#	Time	Username	Problem	Language	Result	Execution time	Memory
170529		oolimry	Werewolf (IOI18_werewolf)	C++14	100 / 100	807 ms	69904 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

const int maxN = 400000;
typedef pair<int,int> ii;
struct UFDS{
	int p[maxN];
	void reset(int n){
		for(int i = 0;i < n;i++) p[i] = i;
	}
	int findSet(int u){
		if(p[u] == u) return u;
		else{
			p[u] = findSet(p[u]);
			return p[u]; ///use path compression only
		}
	}
	void unionSet(int u, int v){
		u = findSet(u);
		v = findSet(v);
		if(u == v) return;
		if(u > v) swap(u,v);
		p[u] = v; ///don't union by rank, instead return the largest value to make tree building easier
	}
};

struct query{
	int start;
	int end;
	int L;
	int R;
	int id;
	int humanSubtree; ///idx of subtree
	int humanLow; ///preorder left endpoint
	int humanHigh; ///preorder right endpoint
	int wolfSubtree; ///idx of subtree
	int wolfLow; ///preorder left endpoint
	int wolfHigh; ///preorder right endpoint
};

struct edge{
	int u;
	int v;
	int w;
};

struct tree{
	vector<int> child[maxN];
	int low[maxN];
	int high[maxN];
	int cnt = 0;
	void addEdge(int parent, int c){
		child[parent].push_back(c);
	}
	
	///basically like a preorder, but don't label the non-leaves
	void dfs(int u){
		low[u] = 102345678;
		high[u] = -1;
		if(child[u].empty()){
			low[u] = cnt;
			high[u] = cnt;
			cnt++;
			return;
		}
		for(int v : child[u]){
			dfs(v);
			low[u] = min(low[u],low[v]);
			high[u] = max(high[u],high[v]);
		}
	}
};

struct segment{
	int seg[maxN]; int n;
	void create(int nn){
		n = nn;
		for(int i = 0;i < 2*n;i++) seg[i] = -1e8;
	}
	
	void update(int i, int v){
		i += n;
		while(i > 0){
			seg[i] = max(seg[i],v);
			i >>= 1;
		}
	}
	
	int Query(int l, int r){
		int ans = -1e8;
		for(l += n, r += n;l < r;l >>= 1, r >>= 1){
			if(l&1){
				ans = max(ans, seg[l]);
				l++;
			}
			if(r&1){
				r--;
				ans = max(ans, seg[r]);
			}
		}
		return ans;
	}
};

bool edgeComp(edge a, edge b){
	return a.w < b.w;
}

bool queryCompHuman(query a, query b){
	return a.L > b.L;
}

bool queryCompWolf(query a, query b){
	return a.R < b.R;
}

bool queryHighComp(query a, query b){
	return a.humanHigh < b.humanHigh;
}

std::vector<int> check_validity(int n, std::vector<int> X, std::vector<int> Y,
		std::vector<int> S, std::vector<int> E,
		std::vector<int> L, std::vector<int> R) {
			
	int m = X.size();
	int q = S.size();
	
	vector<int> answer;
	answer.assign(q,0);
	
	query queries[q+1];
	for(int i = 0;i < q;i++){
		queries[i] = {S[i],E[i],L[i],R[i],i,-1,-1,-1,-1};
	}
	
	edge edges[m];
	UFDS uf;
	tree human; tree wolf;
	
	///Building the tree for the start/human form
	///In the new tree, if a node has a value X, all leaves in that subtree will be reachable if L = X, (i.e. all leaves nodes have value >= X)
	for(int i = 0;i < m;i++) edges[i] = {X[i],Y[i],min(X[i],Y[i])};
	sort(edges,edges+m,edgeComp);
	reverse(edges,edges+m); ///decreasing weight
	sort(queries,queries+q,queryCompHuman); ///decreasing L
	queries[q].L = -1; ///dummy element to ensure entire tree is comepleted
	uf.reset(2*n);
	int newNode = n;
	int edgePtr = 0;
	
	for(int i = 0;i <= q;i++){
		while(edgePtr < m && edges[edgePtr].w >= queries[i].L){
			int u = uf.findSet(edges[edgePtr].u);
			int v = uf.findSet(edges[edgePtr].v);
			edgePtr++;
			if(u == v) continue;
			
			///connect the two greatest parents to another parent
			uf.unionSet(u,newNode);
			uf.unionSet(v,newNode);
			human.addEdge(newNode,u);
			human.addEdge(newNode,v);
			newNode++;	
		}
		
		///the representitive subtree is the subtree of the greatest parent at the current moment
		if(i != q) queries[i].humanSubtree = uf.findSet(queries[i].start);
	}
	
	
	///Building the tree for the end/wolf form
	///In the new tree, if a node has a value X, all leaves in that subtree will be reachable if R = X, (i.e. all leaves nodes have value <= X)
	for(int i = 0;i < m;i++) edges[i] = {X[i],Y[i],max(X[i],Y[i])};
	sort(edges,edges+m,edgeComp); ///increasing weight
	sort(queries,queries+q,queryCompWolf); ///increasing R
	queries[q].R = 1e7; ///dummy element to ensure entire tree is comepleted
	uf.reset(2*n);
	newNode = n;
	edgePtr = 0;
	
	for(int i = 0;i <= q;i++){
		while(edgePtr < m && edges[edgePtr].w <= queries[i].R){
			int u = uf.findSet(edges[edgePtr].u);
			int v = uf.findSet(edges[edgePtr].v);
			edgePtr++;
			if(u == v) continue;
			
			///connect the two greatest parents to another parent
			uf.unionSet(u,newNode);
			uf.unionSet(v,newNode);
			wolf.addEdge(newNode,u);
			wolf.addEdge(newNode,v);
			newNode++;	
		}
		
		///the representitive subtree is the subtree of the greatest parent at the current moment
		if(i != q) queries[i].wolfSubtree = uf.findSet(queries[i].end);
	}
	
	///Now, we run a preorder on the tree, but don't label to edges. This way, we can convert each query into checking whether two sets of elements have any element in common
	human.dfs(2 * n - 2);
	wolf.dfs(2 * n - 2);
	
	
	///Low and High represent the ranges, we need to check if the human range and the wolf range intersect
	///Note: intersect here means the following:
	///In each of the human tree, each node on the original graph corresponds to another number on the human tree
	///Same for the wolf tree
	///Each query is a consecutive range of numbers of both trees.
	///If we convert each of the numbers in the ranges of the trees back to the original index, we query whether there exist a vertex that is shared on both graphs
	for(int i = 0;i < q;i++){
		queries[i].humanLow = human.low[queries[i].humanSubtree];
		queries[i].humanHigh = human.high[queries[i].humanSubtree];
		queries[i].wolfLow = wolf.low[queries[i].wolfSubtree];
		queries[i].wolfHigh = wolf.high[queries[i].wolfSubtree];
	}
	
	///Use a segment tree to answer this type of queries
	segment seg;
	seg.create(n);
	
	///convert stores which number of the human tree corresponds to which number on the wolf tree
	ii convert[n];
	for(int i = 0;i < n;i++) convert[i] = ii(human.low[i],wolf.low[i]);
	sort(convert,convert + n);
	sort(queries,queries+q,queryHighComp);
	
	
	///So basically we build a range max segment tree on the wolf indeces
	///For all human indeces lower than qu.humanHigh, we update the human index on the wolf segment tree
	///If the range max of the wolf segment tree is larger than q.humanLow, then we can conclude that the two ranges intersect
	int ptr = 0;
	for(int i = 0;i < q;i++){
		query qu = queries[i];
		while(ptr < n && qu.humanHigh >= convert[ptr].first){
			seg.update(convert[ptr].second, convert[ptr].first);
			ptr++;
		}
		if(seg.Query(qu.wolfLow, qu.wolfHigh + 1) >= qu.humanLow){
			answer[qu.id] = 1;
		}
		else{
			answer[qu.id] = 0;
		}
	}
	

	return answer;
}

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