Submission #288198

#	Time	Username	Problem	Language	Result	Execution time	Memory
288198		user202729	Simurgh (IOI17_simurgh)	C++17	0 / 100	1 ms	256 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]){
				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;
										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){ // guessed incorrectly, must fix values
									assert(backValue==0);
									backValue=1;

									for(int y=node; y!=x; y=par[y]){
										assert(value[y]==0); value[y]=1;
									}

								}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

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

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:72:1: warning: label 'anyUndefined' defined but not used [-Wunused-label]
   72 | anyUndefined:
      | ^~~~~~~~~~~~

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