oj.uz

Submission #288215

# Submission time Handle Problem Language Result Execution time Memory
288215 2020-09-01T10:15:19 Z user202729 Simurgh (IOI17_simurgh) C++17
32 / 100
 532 ms 14332 KB 
// 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[parIndex[y]]==0); value[parIndex[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

	auto const treeEdges=std::move(tmp); tmp.clear();
	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)->void{
		Dsu dsu(n);
		std::for_each(first, last,[&](int index){
			assert(value[index]<0);
			dsu.join(u[index], v[index]);
		});
		if(first==last) return;

		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);

		int const count=count_common_roads(tmp)-extra;
		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{
			auto const middle=first+((last-first)>>1);
			process(process, first, middle);
			process(process, middle, last);
		}
	};

	for(auto& [dsu, edges]: trees){
		process(process, begin(edges), end(edges));
		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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB correct
2 Correct 0 ms 256 KB correct
3 Correct 1 ms 256 KB correct
4 Correct 0 ms 256 KB correct
5 Correct 0 ms 256 KB correct
6 Correct 0 ms 256 KB correct
7 Correct 0 ms 256 KB correct
8 Correct 0 ms 256 KB correct
9 Correct 0 ms 256 KB correct
10 Correct 0 ms 256 KB correct
11 Correct 1 ms 256 KB correct
12 Correct 0 ms 256 KB correct
13 Correct 0 ms 256 KB correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB correct
2 Correct 0 ms 256 KB correct
3 Correct 1 ms 256 KB correct
4 Correct 0 ms 256 KB correct
5 Correct 0 ms 256 KB correct
6 Correct 0 ms 256 KB correct
7 Correct 0 ms 256 KB correct
8 Correct 0 ms 256 KB correct
9 Correct 0 ms 256 KB correct
10 Correct 0 ms 256 KB correct
11 Correct 1 ms 256 KB correct
12 Correct 0 ms 256 KB correct
13 Correct 0 ms 256 KB correct
14 Correct 3 ms 384 KB correct
15 Correct 3 ms 384 KB correct
16 Correct 3 ms 384 KB correct
17 Correct 2 ms 384 KB correct
18 Correct 1 ms 384 KB correct
19 Correct 2 ms 384 KB correct
20 Correct 2 ms 384 KB correct
21 Correct 2 ms 384 KB correct
22 Correct 1 ms 384 KB correct
23 Correct 1 ms 384 KB correct
24 Correct 1 ms 384 KB correct
25 Correct 0 ms 256 KB correct
26 Correct 1 ms 384 KB correct
27 Correct 1 ms 384 KB correct
28 Correct 1 ms 384 KB correct
29 Correct 1 ms 256 KB correct
30 Correct 1 ms 512 KB correct
31 Correct 1 ms 384 KB correct
32 Correct 1 ms 384 KB correct
33 Incorrect 67 ms 14332 KB WA in grader: NO

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB correct
2 Correct 0 ms 256 KB correct
3 Correct 1 ms 256 KB correct
4 Correct 0 ms 256 KB correct
5 Correct 0 ms 256 KB correct
6 Correct 0 ms 256 KB correct
7 Correct 0 ms 256 KB correct
8 Correct 0 ms 256 KB correct
9 Correct 0 ms 256 KB correct
10 Correct 0 ms 256 KB correct
11 Correct 1 ms 256 KB correct
12 Correct 0 ms 256 KB correct
13 Correct 0 ms 256 KB correct
14 Correct 3 ms 384 KB correct
15 Correct 3 ms 384 KB correct
16 Correct 3 ms 384 KB correct
17 Correct 2 ms 384 KB correct
18 Correct 1 ms 384 KB correct
19 Correct 2 ms 384 KB correct
20 Correct 2 ms 384 KB correct
21 Correct 2 ms 384 KB correct
22 Correct 1 ms 384 KB correct
23 Correct 1 ms 384 KB correct
24 Correct 1 ms 384 KB correct
25 Correct 0 ms 256 KB correct
26 Correct 1 ms 384 KB correct
27 Correct 1 ms 384 KB correct
28 Correct 1 ms 384 KB correct
29 Correct 1 ms 256 KB correct
30 Correct 1 ms 512 KB correct
31 Correct 1 ms 384 KB correct
32 Correct 1 ms 384 KB correct
33 Incorrect 67 ms 14332 KB WA in grader: NO

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB correct
2 Correct 0 ms 256 KB correct
3 Correct 298 ms 5112 KB correct
4 Correct 526 ms 6776 KB correct
5 Correct 527 ms 6936 KB correct
6 Correct 530 ms 7016 KB correct
7 Correct 527 ms 6776 KB correct
8 Correct 529 ms 6956 KB correct
9 Correct 527 ms 7004 KB correct
10 Correct 520 ms 6776 KB correct
11 Correct 522 ms 6904 KB correct
12 Correct 532 ms 6860 KB correct
13 Correct 0 ms 256 KB correct
14 Correct 525 ms 7004 KB correct
15 Correct 529 ms 6904 KB correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB correct
2 Correct 0 ms 256 KB correct
3 Correct 1 ms 256 KB correct
4 Correct 0 ms 256 KB correct
5 Correct 0 ms 256 KB correct
6 Correct 0 ms 256 KB correct
7 Correct 0 ms 256 KB correct
8 Correct 0 ms 256 KB correct
9 Correct 0 ms 256 KB correct
10 Correct 0 ms 256 KB correct
11 Correct 1 ms 256 KB correct
12 Correct 0 ms 256 KB correct
13 Correct 0 ms 256 KB correct
14 Correct 3 ms 384 KB correct
15 Correct 3 ms 384 KB correct
16 Correct 3 ms 384 KB correct
17 Correct 2 ms 384 KB correct
18 Correct 1 ms 384 KB correct
19 Correct 2 ms 384 KB correct
20 Correct 2 ms 384 KB correct
21 Correct 2 ms 384 KB correct
22 Correct 1 ms 384 KB correct
23 Correct 1 ms 384 KB correct
24 Correct 1 ms 384 KB correct
25 Correct 0 ms 256 KB correct
26 Correct 1 ms 384 KB correct
27 Correct 1 ms 384 KB correct
28 Correct 1 ms 384 KB correct
29 Correct 1 ms 256 KB correct
30 Correct 1 ms 512 KB correct
31 Correct 1 ms 384 KB correct
32 Correct 1 ms 384 KB correct
33 Incorrect 67 ms 14332 KB WA in grader: NO