Submission #715169

#	Time	Username	Problem	Language	Result	Execution time	Memory
715169		CyberCow	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1689 ms	428124 KiB

bitaro

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <string>
#include <cmath>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <fstream>
#include <iomanip>
#include <iterator>
#include <stack>
#include <deque>
#define ff first
#define ss second
using namespace std;
using ll = long long;
int const N = 200005;
vector<int> v[N];
vector<int> vr[N];
vector<pair<int, int>> has[N];
int color[N];
int dp[N];
int ind[N];
int ogt[N];
int sq = 300;

void solve()
{
	int n, i, j, m, x, y, a, b, c, q;
	cin >> n >> m >> q;
	for (i = 0; i < m; i++)
	{
		cin >> x >> y;
		v[x].push_back(y);
		vr[y].push_back(x);
	}
	for (i = 1; i <= n; i++)
	{
		for (int gg = 0; gg <= sq; gg++)
		{
			pair<int, int> ma = { -1, -1 };
			for (j = 0; j < vr[i].size(); j++)
			{
				while (gg && ind[vr[i][j]] < has[vr[i][j]].size() && ogt[has[vr[i][j]][ind[vr[i][j]]].second] == 1)
				{
					ind[vr[i][j]]++;
				}
				if (ind[vr[i][j]] < has[vr[i][j]].size())
				{
					ma = max(ma, has[vr[i][j]][ind[vr[i][j]]]);
				}
			}
			if (ma == make_pair(-1, -1))
			{
				break;
			}
			has[i].push_back(ma);
			has[i].back().first++;
			ogt[ma.second] = 1;
		}
		for (j = 0; j < vr[i].size(); j++)
		{
			ind[vr[i][j]] = 0;
		}
		has[i].push_back({ 0, i });
		for (j = 0; j < has[i].size(); j++)
		{
			ogt[has[i][j].second] = 0;
		}
	}
	for (i = 0; i < q; i++)
	{
		cin >> x >> y;
		vector<int> nsh;
		for (j = 0; j < y; j++)
		{
			cin >> c;
			nsh.push_back(c);
			color[c] = -1;
		}
		if (y >= sq)
		{
			for (j = 1; j <= x; j++)
			{
				dp[j] = -1;
			}
			for (j = 1; j <= x; j++)
			{
				if (color[j] == 0)
					dp[j] = max(dp[j], 0);
				if (dp[j] != -1)
					for (int h = 0; h < v[j].size(); h++)
					{
						dp[v[j][h]] = max(dp[v[j][h]], dp[j] + 1);
					}
			}
			cout << dp[x] << '\n';
		}
		else
		{
			int st = 1;
			for (j = 0; j < has[x].size(); j++)
			{
				if (color[has[x][j].second] == 0)
				{
					cout << has[x][j].first << '\n';
					st = 0;
					break;
				}
			}
			if (st)
				cout << -1 << '\n';
		}
		for (j = 0; j < nsh.size(); j++)
		{
			color[nsh[j]] = 0;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int tt = 1;
	//cin >> tt;
	while (tt--)
	{
		solve();
	}
	return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'void solve()':
bitaro.cpp:45:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |    for (j = 0; j < vr[i].size(); j++)
      |                ~~^~~~~~~~~~~~~~
bitaro.cpp:47: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]
   47 |     while (gg && ind[vr[i][j]] < has[vr[i][j]].size() && ogt[has[vr[i][j]][ind[vr[i][j]]].second] == 1)
      |                  ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:51:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     if (ind[vr[i][j]] < has[vr[i][j]].size())
      |         ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:64:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |   for (j = 0; j < vr[i].size(); j++)
      |               ~~^~~~~~~~~~~~~~
bitaro.cpp:69: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]
   69 |   for (j = 0; j < has[i].size(); j++)
      |               ~~^~~~~~~~~~~~~~~
bitaro.cpp:95:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |      for (int h = 0; h < v[j].size(); h++)
      |                      ~~^~~~~~~~~~~~~
bitaro.cpp:105:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |    for (j = 0; j < has[x].size(); j++)
      |                ~~^~~~~~~~~~~~~~~
bitaro.cpp:117:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |   for (j = 0; j < nsh.size(); j++)
      |               ~~^~~~~~~~~~~~
bitaro.cpp:32:24: warning: unused variable 'a' [-Wunused-variable]
   32 |  int n, i, j, m, x, y, a, b, c, q;
      |                        ^
bitaro.cpp:32:27: warning: unused variable 'b' [-Wunused-variable]
   32 |  int n, i, j, m, x, y, a, b, c, q;
      |                           ^

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