Submission #288233

#	Time	Username	Problem	Language	Result	Execution time	Memory
288233		user202729	Simurgh (IOI17_simurgh)	C++17	100 / 100	425 ms	7032 KiB

simurgh

// moreflags=grader.cpp
// 11
#include "simurgh.h"
#if not LOCAL
#define NDEBUG
#endif
#include<cassert>
#include<algorithm>

struct Dsu{
	std::vector<int> data;
	Dsu(int number){reset(number);}
	void reset(int number){data.assign(number, -1);}
	int root(int node){return data[node]>=0 ? data[node]=root(data[node]): node;}
	bool join(int first, int sec){
		first=root(first); sec=root(sec);
		if(first==sec) return false;
		data[first]=sec;
		return true;
	}
};

struct Edge{int node, index;};
std::vector<std::vector<Edge>> add;
std::vector<int> par, depth, parIndex;
std::vector<char> visited;

void work(int node, int curPar, int curDepth){
	par[node]=curPar; depth[node]=curDepth;
	assert(not visited[node]); visited[node]=true;
	for(auto [child, index]: add[node]) if(not visited[child]){
		parIndex[child]=index;
		work(child, node, curDepth+1);
	}
}

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
	// construct a DFS tree
	add.resize(n);
	for(int index=0; index<(int)u.size(); ++index){
		auto const first=u[index], sec=v[index];
		add[first].push_back({sec, index});
		add[sec].push_back({first, index});
	}
	par.resize(n); depth.resize(n);
	visited.assign(n, false);
	parIndex.resize(n); parIndex[0]=-1;
	work(0, -1, 0);

	// compute value of that tree
	std::vector<int> tmp; tmp.reserve(n-1);
	for(int node=0; node<n; ++node)
		for(auto [other, index]: add[node]) if(depth[other]==depth[node]-1)
			tmp.push_back(index);
	int const treeValue=count_common_roads(tmp);

	// compute individual edges' values
	std::vector<int> value(u.size(), -1);
	for(int node=0; node<n; ++node){
		for(auto [other, backIndex]: add[node]) if(depth[other]<depth[node]-1){
			// back edge
			int& backValue=value[backIndex];
			assert(backValue==-1);

			for(int x=node; x!=other; x=par[x]){
				if(value[parIndex[x]]<0) goto anyUndefined;
			}
			continue;

anyUndefined:
			bool guessBackValue=true;
			backValue=0; // this is the guess.


			for(int x=node; x!=other; x=par[x]){
				auto const fixWrongBackValueGuess=[&]{
					for(int y=node; y!=x; y=par[y]){
						assert(value[parIndex[y]]==0); value[parIndex[y]]=1;
					}
				};
			
				int& curValue=value[parIndex[x]];
				if(guessBackValue or curValue<0){
					auto const iterator=std::find(begin(tmp), end(tmp), parIndex[x]);
					*iterator=backIndex;
					auto const v=count_common_roads(tmp)-treeValue; // == backValue-curValue
					*iterator=parIndex[x];

					switch(v){
						case 0:
							{
								if(curValue>=0){
									if(guessBackValue){
										assert(backValue==0); backValue=curValue;
										if(curValue==1) fixWrongBackValueGuess();

										guessBackValue=false;
									}else{
										assert(curValue==backValue);
									}
								}else{
									curValue=backValue;
								}
								break;
							}
						case -1:
							{
								assert(curValue!=0); curValue=1;
								assert(backValue==0);
								if(guessBackValue){
									guessBackValue=false; // already guessed correctly
								}
								break;
							}
						case 1:
							{
								assert(v==1);
								assert(curValue!=1);
								if(guessBackValue){
									assert(backValue==0); backValue=1;
									fixWrongBackValueGuess();
								}else assert(backValue==1);
								curValue=0; backValue=1; guessBackValue=false;
								break;

							}
						default:
							assert(false); __builtin_unreachable();
					}
				}
			}

			if(guessBackValue){
				assert(backValue==0);
				for(int x=node; x!=other; x=par[x])
					assert(value[parIndex[x]]==0);
				// also guessed correctly (there's no way the values of all those edges can be 1 at the same time)
			}
		}
	}

	// double check that tmp is the DFS tree
	for(int node=0; node<n; ++node)
		for(auto [other, index]: add[node]) if(depth[other]==depth[node]-1){
			assert(std::find(begin(tmp), end(tmp), index)!=tmp.end());
		}

	for(auto index: tmp)
		if(value[index]==-1) value[index]=1; // a bridge

	auto const treeEdges=std::move(tmp); tmp.clear();
	tmp.reserve(n-1);
	std::vector<std::pair<Dsu, std::vector<int>>> trees;
	trees.push_back({Dsu(n), {}});
	for(int index=0; index<(int)value.size(); ++index)
		if(value[index]<0){
			[&]{
				if(not trees.back().second.empty())
					trees.push_back({Dsu(n), {}});
				for(auto& [dsu, edges]: trees){
					if(dsu.join(u[index], v[index])){
						edges.push_back(index); return;
					}
				}
				assert(false); __builtin_unreachable();
			}();
		}
	while(not trees.empty() and trees.back().second.empty()) trees.pop_back();
	assert((int)trees.size()<=n-1);

	assert(tmp.empty());

	auto const process=[&](auto process, auto first, auto last, int count // -1: unknown
			)->int /* count */{
		if(count<0){
			Dsu dsu(n);
			std::for_each(first, last,[&](int index){
				assert(value[index]<0);
				dsu.join(u[index], v[index]);
			});
			if(first==last) return 0;

			assert(tmp.empty()); tmp.assign(first, last);

			int extra=0;
			for(auto index: treeEdges) if(dsu.join(u[index], v[index])){
				assert(value[index]>=0); extra+=value[index];
				tmp.push_back(index);
			}
			assert((int)tmp.size()==n-1);

			count=count_common_roads(tmp)-extra;
		}

#if LOCAL
		auto const store=tmp;
#endif
		tmp.clear();
		if(count==last-first)
			std::for_each(first, last,[&](int index){ value[index]=1; });
		else if(count==0)
			std::for_each(first, last,[&](int index){ value[index]=0; });
		else{
			assert(0<count); assert(count<last-first);
			auto const middle=first+((last-first)>>1);
			auto const count1=process(process, first, middle, -1);
			assert(count1<=count);
			process(process, middle, last, count-count1);
		}

		assert(count>=0);
		return count;
	};

	for(auto& [dsu, edges]: trees){
		process(process, begin(edges), end(edges), -1);
		edges.clear();
	}
	trees.clear();

	assert(tmp.empty());
	for(int index=0; index<(int)value.size(); ++index){
		assert(value[index]>=0);
		if(value[index]) tmp.push_back(index);
	}
	return tmp;
}

• Subtask 1: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 21 / 21
• Subtask 4: 19 / 19
• Subtask 5: 30 / 30