Submission #298850

#	Time	Username	Problem	Language	Result	Execution time	Memory
298850		user202729	Werewolf (IOI18_werewolf)	C++17	15 / 100	4029 ms	43028 KiB

werewolf

// moreflags=grader.cpp
// upsolve
// if I can't can't solve it in 5 hours, it's the same as if I can't solve it at all.
// As expected of an IOI problem, the implementation is not hard.

#include "werewolf.h"
#include<vector>
#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

	std::vector<int> result(S.size());
	for(int query=0; query<(int)S.size(); ++query){
		int node1=S[query];
		while(greaterPar[node1]>=L[query]) node1=greaterPar[node1];

		int node2=N-1-E[query];
		while(lessPar[node2]>=N-1-R[query]) node2=lessPar[node2];

		// call handle on all children of node in preorder
		auto iterate=[&](auto iterate, int node, std::vector<std::vector<int>> const& add, auto handle)->void{
			handle(node);
			for(auto other: add[node])
				iterate(iterate, other, add, handle);
		};

		std::vector<char> mark(N);
		iterate(iterate, node1, greaterAdd, [&](int node){ mark[node]=true; });
		bool okay=false;
		iterate(iterate, node2, lessAdd, [&](int node){ okay=okay or mark[N-1-node]; });
		result[query]=okay;
	}

	return result;
}

Compilation message (stderr)

werewolf.cpp: In lambda function:
werewolf.cpp:55:17: warning: unused variable 'success' [-Wunused-variable]
   55 |      auto const success=dsu.join(index, other);
      |                 ^~~~~~~

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