Submission #95052

#	Time	Username	Problem	Language	Result	Execution time	Memory
95052		ckodser	Bitaro’s Party (JOI18_bitaro)	C++14	14 / 100	1771 ms	421700 KiB

bitaro

#include<bits/stdc++.h>
#define pb push_back
#define x first
#define y second
using namespace std;
const int N = 100745, SQ = 319;
int n, m, q, dp[N], M[N], mark[N];
vector < int > in[N], out[N];
vector < pair < int , int > > best[N];
void DFS(int v)
{
	M[v] = 1;
	for (int &u : out[v])
	{
		if (!M[u])
			DFS(u);
		dp[v] = max(dp[v], dp[u] + 1);
	}
}
inline int Brute(int v, vector < int > vec)
{
	memset(M, 0, sizeof(M));
	memset(dp, -63, sizeof(dp));
	M[v] = 1; dp[v] = 0;
	for (int i = 1; i < v; i++)
		if (!M[i]) DFS(i);

	for (int &u : vec)
		M[u] = 2;

	int Mx = -1;
	for (int i = 1; i <= v; i++)
		if (M[i] != 2)
			Mx = max(Mx, dp[i]);
	return (Mx);
}
int main()
{
	scanf("%d%d%d", &n, &m, &q);
	for (int i = 1; i <= m; i++)
	{
		int v, u;
		scanf("%d%d", &v, &u);
		out[v].pb(u);
		in[u].pb(v);
	}

	for (int v = 1; v <= n; v++)
	{
		in[v].pb(0);
		best[0] = {{-1, v}};

		int d = (int)in[v].size();

		vector < int > ptr(d, 0);

		for (int j = 0; j < SQ; j++)
		{
			int id = -1;
			pair < int , int > Mx = {-1, -1};
			for (int i = 0; i < d; i++)
			{
				int &u = in[v][i];
				if (ptr[i] == (int)best[u].size())
					continue;

				if (Mx.first < best[u][ptr[i]].first + 1)
				{
					Mx = best[u][ptr[i]];
					Mx.first ++;
					id = i;
				}
			}
			if (id == -1)
				break;

			ptr[id] ++;
			best[v].pb(Mx);
		}
	}

	for (int ts = 1; ts <= q; ts ++)
	{
		int v, len;
		vector < int > vec;
		scanf("%d%d", &v, &len);
		vec.resize(len);
		for (int i = 0; i < len; i++)
		{
			scanf("%d", &vec[i]);
			mark[vec[i]] = ts;
		}

		if (vec.size() >= SQ - 2)
		{
			printf("%d\n", Brute(v, vec));
			continue;
		}

		int Mx = -1;
		for (auto X : best[v])
		{
			if (mark[X.second] < ts)
			{
				Mx = X.first;
				break;
			}
		}
		printf("%d\n", Mx);
	}
	return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &m, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &v, &u);
   ~~~~~^~~~~~~~~~~~~~~~
bitaro.cpp:86:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &v, &len);
   ~~~~~^~~~~~~~~~~~~~~~~~
bitaro.cpp:90:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &vec[i]);
    ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 0 / 86