Submission #298856

#	Time	Username	Problem	Language	Result	Execution time	Memory
298856		user202729	Werewolf (IOI18_werewolf)	C++17	100 / 100	1367 ms	124584 KiB

werewolf

// moreflags=grader.cpp

#include "werewolf.h"
#include<vector>
#include<set>
#include<climits>
#include<algorithm>
#if not LOCAL
#define NDEBUG
#endif
#include<cassert>

struct Dsu{ // with path compression but without union by rank
	std::vector<int> data; // positive: parent, negative: ~(minimum in component)
	Dsu(int number): data(number){
		for(int node=0; node<number; ++node)
			data[node]=~ node;
	}
	int root(int node){return data[node]>=0 ? data[node]=root(data[node]): node;}
	int minimumInComponent(int node){
		return ~data[root(node)];
	}
	bool join(int first, int sec){
		first=root(first); sec=root(sec);
		if(first==sec) return false;
		data[first]=std::max(data[first], data[sec]); // inverted
		data[sec]=first;
		return true;
	}
};

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) {
	std::vector<std::vector<int>> greaterAdd(N), lessAdd(N);
	for(int index=0; index<(int)X.size(); ++index){
		auto const [a, b]=std::minmax({X[index], Y[index]});
		assert(a!=b);
		greaterAdd[a].push_back(b);
		lessAdd[N-1-b].push_back(N-1-a);
	}

	auto const process=[&](std::vector<std::vector<int>>& add)->std::vector<int>{
		// add: adjacency list (elements of list [i] must be strictly greater than i)
		// also reuse add for the children of the resulting par
		// (node n is for -1)
		std::vector<int> par(add.size(), -1);
		Dsu dsu((int)add.size());
		for(auto index=(int)add.size(); index--;){
			for(auto other: add[index]){
				other=dsu.minimumInComponent(other);
				if(other>index){
					auto const success=dsu.join(index, other);
					assert(success);
					assert(par[other]==-1);
					par[other]=index;
				}else assert(other==index);
			}
		}

		for(auto& it: add) it.clear();
		add.emplace_back();
		for(int node=0; node<(int)par.size(); ++node){
			(par[node]<0 ? add.back(): add[par[node]]).push_back(node);
		}

		return par;
	};

	std::vector<int> greaterPar=process(greaterAdd);
	std::vector<int> lessPar=process(lessAdd);
	// greaterPar: the equivalent structure of traversing with the additional condition (vertex >= L)
	// for some L
	// ( i -> greaterPar[i] ) where greaterPar[i]<i

	// lessPar: vice versa, but with flipped vertex indices

	struct Jump{
		std::vector<std::vector<int>> data;
		// assumes -1 is the virtual root
		Jump(std::vector<int> value): data{std::move(value)}{
			for(int step=1; step<(int)data.back().size(); step<<=1){
				std::vector<int> const& a=data.back();
				auto b=a;
				bool useful=false;
				for(auto& it: b) if(it>=0){
					it=a[it];
					if(it>=0) useful=true;
				}
				if(useful)
					data.push_back(std::move(b));
				else break;
			}
		}
		int get(int node, int least)const{
			// assumes par[node]<node for all node, find minimum ancestor >=least
			for(auto layer=data.size(); layer--;)
				if(data[layer][node]>=least) node=data[layer][node];
			return node;
		}
	};
	Jump greaterJump(std::move(greaterPar)), lessJump(std::move(lessPar));

	struct Query{int node, index;};
	std::vector<std::vector<Query>> queries(N);
	// [node1] = (node2, query): query with index==query -> greater subtree rooted at node1
	// has any common vertex with less subtree rooted at node2?

	for(int query=0; query<(int)S.size(); ++query){
		int node1=greaterJump.get(S[query], L[query]);
		int node2=lessJump.get(N-1-E[query], N-1-R[query]);
		queries[node1].push_back({node2, query});
	}

	std::vector<int> result(S.size());

	// solve all queries

	/* // * not necessary
	auto const subtreeSize=[&]{ // of greater
		std::vector<int> result(N);
		auto const work=[&](auto work, int node)->int{
			auto cur=1;
			for(auto other: greaterAdd[node])
				cur+=work(work, other);
			return result[node]=cur;
		};
		for(auto it: greaterAdd[N]) work(work, it);
		for(auto it: result) assert(it>0);
		return result;
	}();
	*/

	auto const merge=[&](std::set<int> first, std::set<int> sec){
		if(first.size()<sec.size()) std::swap(first, sec);
		for(auto it: sec){
			auto const success=first.insert(it).second;
			assert(success);
		}
		return first;
	};

	std::vector<int> lessFirst(N), lessLast(N); // first and last index in preorder traversal of the less tree
	{ // construct ^
		int cur=0;
		auto const work=[&](auto work, int node)->void{
			assert(lessFirst[node]==0);
			lessFirst[node]=cur++;
			for(auto other: lessAdd[node])
				work(work, other);
			lessLast[node]=cur;
		};
		for(auto node: lessAdd[N]){
			work(work, node);
		}
		assert(cur==N);
	}

	// wait it's not necessary to compute subtreeSize if std::set is used anyway
	auto const work=[&](auto work, int node)->std::set<int>{
		std::set<int> curSet{lessFirst[N-1-node]};
		for(auto other: greaterAdd[node])
			curSet=merge(std::move(curSet), work(work, other));
		for(auto [node2, queryIndex]: queries[node]){
			auto const iterator=curSet.lower_bound(lessFirst[node2]);
			if(iterator!=curSet.end() and *iterator<lessLast[node2])
				result[queryIndex]=1;
		}
		return curSet;
	};
	for(auto it: greaterAdd[N]) work(work, it);

	return result;
}

Compilation message (stderr)

werewolf.cpp: In lambda function:
werewolf.cpp:53:17: warning: unused variable 'success' [-Wunused-variable]
   53 |      auto const success=dsu.join(index, other);
      |                 ^~~~~~~
werewolf.cpp: In lambda function:
werewolf.cpp:137:15: warning: unused variable 'success' [-Wunused-variable]
  137 |    auto const success=first.insert(it).second;
      |               ^~~~~~~

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