제출 #286230

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
286230		user202729	장난감 기차 (IOI17_train)	C++17	0 / 100	10 ms	3072 KiB

train

// moreflags=grader.cpp
//
// 13
// subtask (all owned by A)
// 
#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])
		work(other);
	component.push_back(node);
}

std::vector<int> awin;
void work3(int node){
	assert(not state[node]); state[node]=true;
	for(auto other: reverse[node]) if(not state[other])
		work(other);
	awin[node]=true;
}

std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
	if(not std::all_of(begin(a), end(a),[&](char it){return it;})) return {};

	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);
	}
	order.clear(); order.reserve(a.size());
	state.assign(a.size(), false);
	for(int node=0; node<(int)a.size(); ++node)
		if(not state[node])
			work(node);
	assert(order.size()==a.size());
	assert(std::all_of(begin(state), end(state),[&](char it){return it;}));

	awin.assign(a.size(), false);
	std::for_each(order.rbegin(), order.rend(),[&](int node){
		if(state[node]){
			component.clear();
			work2(node);

			bool const okay=component.size()>1 and std::any_of(begin(component), end(component),
					[&](int it){return r[it];});
			if(okay)
				for(auto it: component) awin[it]=true;
		}
	});
	assert(std::all_of(begin(state), end(state),[&](char it){return not it;}));

	for(int node=0; node<(int)a.size(); ++node)
		if(awin[node] and not state[node])
			work3(node);
	return std::move(awin);
}

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