Submission #475847

#	Time	Username	Problem	Language	Result	Execution time	Memory
475847		prvocislo	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	765 ms	168504 KiB

bitaro

#include <iostream>
#include <vector>
using namespace std;

const int maxn = 1e5 + 5, sq = 200;
int n, m, q, bad[maxn], dp[maxn];
vector<int> g[maxn];
vector<pair<int, int> > best[maxn];
void upd(int& a, const int& b) { a = max(a, b); }
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m >> q;
	for (int i = 0, a, b; i < m; i++)
	{
		cin >> a >> b;
		g[--a].push_back(--b);
	}
	for (int i = 0; i < n; i++)
	{
		for (pair<int, int>& j : best[i]) j.first++;
		if (best[i].size() < sq) best[i].push_back({ 0, i });
		for (int j : g[i])
		{
			vector<pair<int, int> > v;
			int pi = 0, pj = 0;
			while (v.size() < sq && (pi < best[i].size() || pj < best[j].size()))
			{
				while (pi < best[i].size() && bad[best[i][pi].second]) pi++;
				while (pj < best[j].size() && bad[best[j][pj].second]) pj++;
				if (pi < best[i].size() && (pj == best[j].size() || best[i][pi].first > best[j][pj].first))
					v.push_back(best[i][pi++]);
				else if (pj < best[j].size())
					v.push_back(best[j][pj++]);
			}
			for (pair<int, int> vi : v) bad[vi.second] = 0;
			best[j] = v;
		}
	}
	while (q--)
	{
		int u, s;
		cin >> u >> s; u--;
		vector<int> c(s);
		for (int i = 0; i < s; i++)
		{
			cin >> c[i];
			bad[--c[i]] = 1;
		}
		if (s > sq)
		{
			for (int i = 0; i < n; i++) dp[i] = -1e9;
			for (int i = 0; i <= u; i++)
			{
				if (!bad[i]) upd(dp[i], 0);
				for (int j : g[i]) upd(dp[j], dp[i] + 1);
			}
			cout << max(dp[u], -1) << "\n";
		}
		else
		{
			int ans = -1;
			for (int i = 0; i < best[u].size(); i++) if (!bad[best[u][i].second])
			{
				ans = best[u][i].first;
				break;
			}
			cout << ans << "\n";
		}
		for (int i = 0; i < s; i++) bad[c[i]] = 0;
	}
	return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:28:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |    while (v.size() < sq && (pi < best[i].size() || pj < best[j].size()))
      |                             ~~~^~~~~~~~~~~~~~~~
bitaro.cpp:28:55: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |    while (v.size() < sq && (pi < best[i].size() || pj < best[j].size()))
      |                                                    ~~~^~~~~~~~~~~~~~~~
bitaro.cpp:30:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     while (pi < best[i].size() && bad[best[i][pi].second]) pi++;
      |            ~~~^~~~~~~~~~~~~~~~
bitaro.cpp:31:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     while (pj < best[j].size() && bad[best[j][pj].second]) pj++;
      |            ~~~^~~~~~~~~~~~~~~~
bitaro.cpp:32:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     if (pi < best[i].size() && (pj == best[j].size() || best[i][pi].first > best[j][pj].first))
      |         ~~~^~~~~~~~~~~~~~~~
bitaro.cpp:32:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     if (pi < best[i].size() && (pj == best[j].size() || best[i][pi].first > best[j][pj].first))
      |                                 ~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:34:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     else if (pj < best[j].size())
      |              ~~~^~~~~~~~~~~~~~~~
bitaro.cpp:64:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |    for (int i = 0; i < best[u].size(); i++) if (!bad[best[u][i].second])
      |                    ~~^~~~~~~~~~~~~~~~

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