Submission #714881

#	Time	Username	Problem	Language	Result	Execution time	Memory
714881		CyberCow	Bitaro’s Party (JOI18_bitaro)	C++17	0 / 100	18 ms	8524 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;
}

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 });
		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] == -1)
					dp[j] = 0;
				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: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]
   45 |   while (has[i].size() > sq)
      |          ~~~~~~~~~~~~~~^~~~
bitaro.cpp:49:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for ( j = 0; j < v[i].size(); j++)
      |                ~~^~~~~~~~~~~~~
bitaro.cpp:51: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]
   51 |    for (int h = 0; h < has[i].size(); h++)
      |                    ~~^~~~~~~~~~~~~~~
bitaro.cpp:77:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for (int h = 0; h < v[j].size(); h++)
      |                     ~~^~~~~~~~~~~~~
bitaro.cpp:87: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]
   87 |    for (j = 0; j < has[x].size(); j++)
      |                ~~^~~~~~~~~~~~~~~
bitaro.cpp:99:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |   for ( j = 0; j < nsh.size(); j++)
      |                ~~^~~~~~~~~~~~
bitaro.cpp:34:24: warning: unused variable 'a' [-Wunused-variable]
   34 |  int n, i, j, m, x, y, a, b, c, q;
      |                        ^
bitaro.cpp:34:27: warning: unused variable 'b' [-Wunused-variable]
   34 |  int n, i, j, m, x, y, a, b, c, q;
      |                           ^

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