Submission #137245

#	Time	Username	Problem	Language	Result	Execution time	Memory
137245		MAMBA	Toy Train (IOI17_train)	C++17	0 / 100	14 ms	1660 KiB

train

#include "train.h"
#include <bits/stdc++.h>

using namespace std;

#define rep(i , j ,k) for(int i = j; i < (int)k; i++)
#define pb push_back
#define all(x) x.begin(),x.end()

typedef vector<int> vi;

const int N = 5010;
bitset<N> mark;
bool h[N];
vi adj[N], radj[N];
int col[N], S[N], cnt;

vi vec;

void dfs(int v) {
	mark[v] = true;
	for (auto e : adj[v])
		if (!mark[e])
			dfs(e);
	vec.pb(v);
}

void dfs2(int v, int w) {
	mark[v] = true;
	col[v] = w;
	S[w]++;
	for (auto e : radj[v])
		if (!mark[e])
			dfs2(e , w);
}

std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
	
	int n = a.size();

	int m = u.size();

	rep(i , 0 , m) {
		adj[u[i]].pb(v[i]);
		radj[v[i]].pb(u[i]);
	}

	bool Bo = false;
	bool Ar = false;

	rep(i , 0 , n) {
		if (a[i]) Ar = true;
		else Bo = true;
	}

	if (Bo == false) {
		rep(i , 0 ,n)
			if (!mark[i])
				dfs(i);
		reverse(all(vec));
		mark.reset();
		for (auto e : vec)
			if (!mark[e])
				dfs2(e , ++cnt);

		vi me(n);
		iota(all(me) , 0);

		sort(all(me) , [&](int x, int y) { return col[x] > col[y]; });

		rep(i , 0 , n)
			if (S[col[i]] > 1) h[col[i]] |= r[i];

		for (auto e : me)
			for (auto e2 : adj[e])
				h[col[e]] |= h[col[e2]];
		
		vi res(n);
		rep(i , 0 , n)
			if (h[col[i]])
				res[i] = 1;
		return res;
	}

	vi res(n);
	for (int i = n - 1; ~i; i--) {
		bool A = false;
		bool B = false;
		for (auto e : adj[i]) {
			if (i == e) {
				if (r[i])
					A = true;
				else 
					B = true;
			}
			else {
				if (res[e])
					A = true;
				else
					B = true;
			}
		}
		if (a[i] && A) res[i] = true;
		if (!a[i] && !B) res[i] = true;
	}

	return res;
}

Compilation message (stderr)

train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:49:7: warning: variable 'Ar' set but not used [-Wunused-but-set-variable]
  bool Ar = false;
       ^~

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