Submission #714893

#	Time	Username	Problem	Language	Result	Execution time	Memory
714893		CyberCow	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	2111 ms	312592 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<pair<int, int>> has[N];
int color[N];
int dp[N];
int sq = 320;

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);
	}
	for ( i = 1; i <= n; i++)
	{
		has[i].push_back({ 0, i });
		vector<pair<int, int>> kop = has[i];
		has[i].clear();
		sort(kop.begin(), kop.end(), xDD);
		for ( j = 0; j < kop.size(); j++)
		{
			if (!j || has[i].back().second != kop[j].second)
				has[i].push_back(kop[j]);
		}
		sort(has[i].begin(), has[i].end(), xD);
		while (has[i].size() > sq)
		{
			has[i].pop_back();
		}
		for ( j = 0; j < v[i].size(); j++)
		{
			for (int h = 0; h < has[i].size(); h++)
			{
				has[v[i][j]].push_back({ has[i][h].first + 1, has[i][h].second });
			}
		}
	}
	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:54: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]
   54 |   for ( j = 0; j < kop.size(); j++)
      |                ~~^~~~~~~~~~~~
bitaro.cpp:60:24: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   60 |   while (has[i].size() > sq)
      |          ~~~~~~~~~~~~~~^~~~
bitaro.cpp:64:18: 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 < v[i].size(); j++)
      |                ~~^~~~~~~~~~~~~
bitaro.cpp:66: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]
   66 |    for (int h = 0; h < has[i].size(); h++)
      |                    ~~^~~~~~~~~~~~~~~
bitaro.cpp:93:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |      for (int h = 0; h < v[j].size(); h++)
      |                      ~~^~~~~~~~~~~~~
bitaro.cpp:103: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]
  103 |    for (j = 0; j < has[x].size(); j++)
      |                ~~^~~~~~~~~~~~~~~
bitaro.cpp:115:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |   for ( j = 0; j < nsh.size(); j++)
      |                ~~^~~~~~~~~~~~
bitaro.cpp:41:24: warning: unused variable 'a' [-Wunused-variable]
   41 |  int n, i, j, m, x, y, a, b, c, q;
      |                        ^
bitaro.cpp:41:27: warning: unused variable 'b' [-Wunused-variable]
   41 |  int n, i, j, m, x, y, a, b, c, q;
      |                           ^

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