Submission #291003

#	Time	Username	Problem	Language	Result	Execution time	Memory
291003		user202729	Werewolf (IOI18_werewolf)	C++17	34 / 100	654 ms	45672 KiB

werewolf

// moreflags=grader.cpp
// 8
#include "werewolf.h"
#include<vector>
#include<climits>
#include<algorithm>
#if not LOCAL
#define NDEBUG
#endif
#include<cassert>

std::vector<int> pos;
struct FatDsu{
	struct Node{
		std::vector<int> children; // excluding itself
		int root=-1;
		std::pair<int, int> rangePos;
	};
	std::vector<Node> data;
	FatDsu(int number): data(number){
		for(int index=0; index<number; ++index)
			data[index].rangePos={pos[index], pos[index]};
	}
	int root(int node) const{
		if(data[node].root>=0) node=data[node].root;
		assert(data[node].root<0);
		return node;
	}
	bool join(int first, int sec){
		first=root(first); sec=root(sec);
		if(first==sec) return false;
		if(data[first].children.size()<data[sec].children.size()) std::swap(first, sec);
		for(auto it: data[sec].children){
			assert(data[it].root==sec);
			assert(data[it].children.empty());
			data[it].root=first;
			data[first].children.push_back(it);
		}
		data[sec].root=first;
		data[sec].children.clear();
		data[first].children.push_back(sec);
		data[first].rangePos={
			std::min(data[first].rangePos.first, data[sec].rangePos.first),
			std::max(data[first].rangePos.second, data[sec].rangePos.second)
		};
		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>> add(N);
	for(int index=0; index<(int)X.size(); ++index){
		add[X[index]].push_back(Y[index]);
		add[Y[index]].push_back(X[index]);
	}

	if((int)X.size()==N-1){
		std::vector<int> order; order.reserve(N);
		{
			auto const index=int(std::find_if(begin(add), end(add), [&](auto const& it){return it.size()==1;})-add.begin());
			order.push_back(index);
			assert(add[index].size()==1); order.push_back(add[index][0]);
		}
		while((int)order.size()!=N){
			if(add[order.back()].size()!=2) return {};
			for(auto it: add[order.back()]) if(it!=order.end()[-2]){
				order.push_back(it);
				break;
			}
		}

		pos.resize(N);
		for(int index=0; index<(int)order.size(); ++index)
			pos[order[index]]=index;
	}


	struct T{int s, e, l, r, index;
		//std::vector<int> erComponent;
		std::pair<int, int> rangePos;
	};
	std::vector<T> queries(S.size());
	for(int index=0; index<(int)queries.size(); ++index)
		queries[index]={S[index], E[index], L[index], R[index], index};

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

	{
		std::sort(begin(queries), end(queries), [&](auto const& first, auto const& sec){
			return first.r<sec.r;
		});
		FatDsu tree(N);
		auto iterator=queries.begin();
		for(int index=0; iterator!=queries.end(); ++index){
			for(auto other: add[index]) if(other<=index)
				tree.join(index, other);
			while(iterator!=queries.end() and iterator->r==index){
				auto const tmp=tree.root(iterator->e);
				//iterator->erComponent=tree.data[tmp].children;
				//iterator->erComponent.push_back(tmp);
				iterator->rangePos=tree.data[tmp].rangePos;
				++iterator;
			}
		}
	}
	{
		std::sort(begin(queries), end(queries), [&](auto const& first, auto const& sec){
			return first.l>sec.l;
		});
		FatDsu tree(N);
		auto iterator=queries.begin();
		for(int index=N-1; iterator!=queries.end(); --index){
			for(auto other: add[index]) if(other>=index)
				tree.join(index, other);
			while(iterator!=queries.end() and iterator->l==index){
				auto const curRoot=tree.root(iterator->s);
				/*
				for(auto it: iterator->erComponent) if(tree.root(it)==curRoot){
					result[iterator->index]=1;
					break;
				}
				*/
				auto const [a, b]=tree.data[curRoot].rangePos;
				auto const [c, d]=iterator->rangePos;
				if(std::max(a, c)<=std::min(b, d))
					result[iterator->index]=1;
				++iterator;
			}
		}
	}
	return result;

}

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