Submission #714973

#	Time	Username	Problem	Language	Result	Execution time	Memory
714973		CyberCow	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	2013 ms	10716 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 = 100005;
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 = 150;

bool xD(const pair<int, int> &a, const pair<int, int> &b)
{
	return a > b;
}

bool xDD(const pair<int, int>& a, const pair<int, int>& b)
{
	if (a.second == b.second)
		return a.first > b.first;
	return a.second < b.second;
}

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]]]);
				}
			}
			for ( j = 0; j < vr[i].size(); j++)
			{
				ind[vr[i][j]] = 0;
			}
			if (ma == make_pair(-1, -1))
			{
				break;
			}
			has[i].push_back(ma);
			has[i].back().first++;
			ogt[ma.second] = 1;
		}
		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:57:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |    for (j = 0; j < vr[i].size(); j++)
      |                ~~^~~~~~~~~~~~~~
bitaro.cpp:59: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]
   59 |     while (gg && ind[vr[i][j]] < has[vr[i][j]].size() && ogt[has[vr[i][j]][ind[vr[i][j]]].second] == 1)
      |                  ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:63: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]
   63 |     if (ind[vr[i][j]] < has[vr[i][j]].size())
      |         ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:68:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |    for ( j = 0; j < vr[i].size(); j++)
      |                 ~~^~~~~~~~~~~~~~
bitaro.cpp:81: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]
   81 |   for ( j = 0; j < has[i].size(); j++)
      |                ~~^~~~~~~~~~~~~~~
bitaro.cpp:107:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |      for (int h = 0; h < v[j].size(); h++)
      |                      ~~^~~~~~~~~~~~~
bitaro.cpp:117: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]
  117 |    for (j = 0; j < has[x].size(); j++)
      |                ~~^~~~~~~~~~~~~~~
bitaro.cpp:129:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |   for ( j = 0; j < nsh.size(); j++)
      |                ~~^~~~~~~~~~~~
bitaro.cpp:44:24: warning: unused variable 'a' [-Wunused-variable]
   44 |  int n, i, j, m, x, y, a, b, c, q;
      |                        ^
bitaro.cpp:44:27: warning: unused variable 'b' [-Wunused-variable]
   44 |  int n, i, j, m, x, y, a, b, c, q;
      |                           ^

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