Submission #380341

#	Time	Username	Problem	Language	Result	Execution time	Memory
380341		ngpin04	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1779 ms	218472 KiB

bitaro

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
const int N = 1e5 + 5;
const int T = 200;

vector <pair <int, int>> best[N];
vector <int> adj[N];

int dp[N];
int n,m,q;

bool vis[N];
bool tmp[N];
 
vector <pair <int, int>> join(const vector <pair <int, int>> &a, const vector <pair <int, int>> &b) {
	vector <pair <int, int>> res;

	for (int i = 0, j = 0; res.size() < T && (i < a.size() || j < b.size());) {
		if (i == a.size() || (j < b.size() && a[i] < b[j])) {
			if (!tmp[b[j].se]) {
				res.push_back(b[j]);
				tmp[b[j].se] = true;
			}
			j++;
		} else {
			if (!tmp[a[i].se]) {
				res.push_back(a[i]);
				tmp[a[i].se] = true;
			}
			i++;
		} 
	}
	for (auto p : res) 
		tmp[p.se] = false;
	return res;
}

void dfs(int u) {
	best[u].push_back(mp(0, u));
	vis[u] = true;
	for (int v : adj[u]) {
		if (!vis[v])
			dfs(v);
		vector <pair <int, int>> b = best[v];
		for (auto &p : b)
			p.fi++;
		best[u] = join(best[u], b);
	}
}

int calc(int u) {
	int &res = dp[u];
	if (res != -1)
		return res;
	res = vis[u] ? -1e9 : 0;
	for (int v : adj[u])
		res = max(res, calc(v) + 1);
	return res;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m >> q;
	for (int i = 1; i <= m; i++) {
		int u,v;
		cin >> u >> v;
		adj[v].push_back(u);
	}

	for (int i = 1; i <= n; i++)
		if (!vis[i])
			dfs(i);

	memset(vis, 0, sizeof(vis));

	while (q--) {
		int u,sz;
		cin >> u >> sz;
		vector <int> node(sz);
		for (int &x : node)
			cin >> x;

		for (int x : node)
			vis[x] = true;
		if (node.size() < T) {
			bool ok = false;
			for (auto p : best[u]) if (!vis[p.se]) {
				cout << p.fi << "\n";
				ok = true;
				break;
			}
			if (!ok)
				cout << -1 << "\n"; 
		} else {
			memset(dp, -1, sizeof(dp));
			int ans = calc(u);
			if (ans < 0)
				cout << -1 << "\n";
			else
				cout << ans << "\n";
		}
		
		for (int x : node)
			vis[x] = false;
	}
	return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'std::vector<std::pair<int, int> > join(const std::vector<std::pair<int, int> >&, const std::vector<std::pair<int, int> >&)':
bitaro.cpp:21:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for (int i = 0, j = 0; res.size() < T && (i < a.size() || j < b.size());) {
      |                                            ~~^~~~~~~~~~
bitaro.cpp:21:62: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for (int i = 0, j = 0; res.size() < T && (i < a.size() || j < b.size());) {
      |                                                            ~~^~~~~~~~~~
bitaro.cpp:22:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |   if (i == a.size() || (j < b.size() && a[i] < b[j])) {
      |       ~~^~~~~~~~~~~
bitaro.cpp:22:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |   if (i == a.size() || (j < b.size() && a[i] < b[j])) {
      |                         ~~^~~~~~~~~~

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