Submission #286384

#	Time	Username	Problem	Language	Result	Execution time	Memory
286384		user202729	Toy Train (IOI17_train)	C++17	100 / 100	1075 ms	1912 KiB

train

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

std::vector<std::vector<int>> add, reverse;

std::vector<int> order;
std::vector<char> state;
void work(int node){
	assert(not state[node]); state[node]=true;
	for(auto other: add[node]) if(not state[other])
		work(other);
	order.push_back(node);
}

std::vector<int> component;
void work2(int node){
	assert(state[node]); state[node]=false;
	for(auto other: reverse[node]) if(state[other])
		work2(other);
	component.push_back(node);
}

std::vector<int> awin;
std::vector<bool> keep;
std::vector<int> outDegree;
std::vector<int> a;

void remove(int node){
	assert(keep[node]);
	keep[node]=false;
	for(auto other: reverse[node]) {
		--outDegree[other];
		assert(outDegree[other]>=0); assert(outDegree[other]<(int)add[other].size());
	}

	for(auto other: reverse[node]) if(keep[other]){
		if(a[other]){
			remove(other);
		}else{
			if(outDegree[other]==0)
				remove(other);
		}
	}
}

void remove2(int node){
	assert(keep[node]);
	keep[node]=false;
	for(auto other: reverse[node]) {
		--outDegree[other];
		assert(outDegree[other]>=0); assert(outDegree[other]<(int)add[other].size());
	}

	for(auto other: reverse[node]) if(keep[other]){
		if(a[other]){
			if(outDegree[other]==0)
				remove2(other);
		}else{
			remove2(other);
		}
	}
}

std::vector<int> who_wins(std::vector<int> a_, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
	::a=std::move(a_);
	add.clear(); reverse.clear();
	add.resize(a.size());
	reverse.resize(a.size());
	for(int index=0; index<(int)u.size(); ++index){
		auto const first=u[index], sec=v[index];
		add[first].push_back(sec); reverse[sec].push_back(first);
	}
 
	awin.assign(a.size(), true);

	bool useful;
	do{
		useful=false;
		/*
		for(int mask=noChargeMask; mask; mask=(mask-1)&noChargeMask){
			for(int node=0; node<(int)a.size(); ++node)
				if(mask>>node&1){
					if(a[node]){
						if(not contains(mask|bwin, adjacent[node]))
							goto next_mask;
					}else{
						if(((mask|bwin)&adjacent[node])==0)
							goto next_mask;
					}
				}
			bwin|=mask;
next_mask:;
		}
 
		for(int node=0; node<(int)a.size(); ++node)
			if(a[node]){
				if(contains(bwin, adjacent[node])) bwin|=1<<node;
			}else{
				if((bwin&adjacent[node])!=0) bwin|=1<<node;
			}
			*/

		keep.assign(a.size(), true);

		outDegree.resize(a.size());
		for(int node=0; node<(int)a.size(); ++node){
			outDegree[node]=(int)add[node].size();
		}

		for(int node=0; node<(int)add.size(); ++node)
			if(keep[node] and r[node] and awin[node])
				remove(node);

		for(int node=0; node<(int)add.size(); ++node){
			if(not awin[node]) assert(keep[node]);
			if(awin[node] and keep[node]){
				useful=true;
				awin[node]=false;
			}
		}

		// ======

		keep.assign(a.size(), true);

		outDegree.resize(a.size());
		for(int node=0; node<(int)a.size(); ++node){
			outDegree[node]=(int)add[node].size();
		}

		for(int node=0; node<(int)add.size(); ++node)
			if(keep[node] and not awin[node])
				remove2(node);

		for(int node=0; node<(int)add.size(); ++node){
			if(not awin[node]) assert(not keep[node]);
			if(awin[node] and not keep[node]){
				useful=true;
				awin[node]=false;
			}
		}
	}while(useful);
 
	return std::move(awin);
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 12 / 12
• Subtask 6: 51 / 51