제출 #95066

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
95066		ckodser	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1506 ms	420728 KiB

bitaro

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

		while ((int)best[v].size() < SQ)
		{
			int id = -1;
			pair < int , int > Mx = {-1, -1};
			for (int i = 0; i < d; i++)
			{
				int &u = in[v][i];
				while (ptr[i] < (int)best[u].size() && mark[best[u][ptr[i]].second] == v)
					ptr[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;

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

	memset(mark, 0, sizeof(mark));
	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 - 10)
		{
			printf("%d\n", Brute(v, vec));
			continue;
		}

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

컴파일 시 표준 에러 (stderr) 메시지

bitaro.cpp: In function 'int main()':
bitaro.cpp:29: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:33: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:81: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:85: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: 86 / 86