oj.uz

Submission #286230

# Submission time Handle Problem Language Result Execution time Memory
286230 2020-08-30T08:35:17 Z user202729 Toy Train (IOI17_train) C++17
0 / 100
 10 ms 3072 KB 
// 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.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 512 KB WA in grader: Wrong returned array size
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 256 KB WA in grader: Wrong returned array size
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 3072 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 640 KB WA in grader: Wrong returned array size
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 640 KB WA in grader: Wrong returned array size
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 512 KB WA in grader: Wrong returned array size
2 Halted 0 ms 0 KB -