제출 #137172

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
137172		random0029	장난감 기차 (IOI17_train)	C++14	100 / 100	370 ms	1656 KiB

train

// ItnoE
#include<bits/stdc++.h>
using namespace std;
const int N = 5005, MXM = 20004;
int n, m, D[N], F[N], M[N], qu[N], DD[N];
bool Bad[N], Can[N];
vector < int > Adj[N], Adt[N];
vector < int > who_wins(vector < int > B, vector < int > S, vector < int > U, vector < int > V)
{
	n = (int)B.size();
	m = (int)U.size();
	for (int i = 0; i < m; i ++)
	{
		Adt[V[i]].push_back(U[i]);
		DD[U[i]] ++;
		D[U[i]] ++;
		F[U[i]] ++;
	}
	bool YAY = 1;
	while (YAY)
	{
		YAY = 0;
		int l = 0, r = 0;
		memset(Bad, 0, sizeof(Bad));
		for (int i = 0; i < n; i ++)
			if (S[i] && !Can[i])
				Bad[i] = 1, qu[r ++] = i;
		for (int i = 0; i < n; i ++)
			D[i] = DD[i];
		while (r - l)
		{
			int v = qu[l ++];
			for (int u : Adt[v])
				if (!Can[u] && !Bad[u])
				{
					if (B[u])
						Bad[u] = 1, qu[r ++] = u;
					else
					{
						D[u] --;
						if (!D[u])
							Bad[u] = 1, qu[r ++] = u;
					}
				}
		}
		l = r = 0;
		for (int i = 0; i < n; i ++)
			if (!Bad[i] && !Can[i])
				Can[i] = 1, qu[r ++] = i, YAY = 1;
		while (r - l)
		{
			int v = qu[l ++];
			for (int u : Adt[v])
				if (!Can[u])
				{
					if (!B[u])
						Can[u] = 1, qu[r ++] = u;
					else
					{
						F[u] --;
						if (!F[u])
							Can[u] = 1, qu[r ++] = u;
					}
				}
		}
	}

	vector < int > res;
	for (int i = 0; i < n; i ++)
		res.push_back(1 - Can[i]);
	return (res);
}

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