Submission #44596

#	Time	Username	Problem	Language	Result	Execution time	Memory
44596		aome	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	2088 ms	296820 KiB

bitaro

#include <bits/stdc++.h>

#define fi first
#define se second

using namespace std;

typedef pair<int, int> ii;

const int N = 100005;
const int M = 335;
const int INF = 1e9;

int n, m, q;
int res;
int deg[N];
int dis[N];
bool vis[N];
vector<int> G[N], buf;
vector<ii> opt[N], vec;

void add(vector<ii> &a, int &A) {
	int id = a[A].second;
	if (!vis[id]) {
		vec.push_back(a[A]);
		vis[id] = 1, buf.push_back(id);
	}
	A++;
}

void Merge(vector<ii> &a, vector<ii> &b) {
	int A = 0, B = 0;
	vec.clear(), buf.clear();
	while (A < a.size() && B < b.size()) {
		if (a[A].first > b[B].first) add(a, A);
		else add(b, B);
	}
	while (A < a.size()) add(a, A);
	while (B < b.size()) add(b, B);
	for (auto i : buf) vis[i] = 0;
	a = vec;
	while (a.size() > M) a.pop_back();
}

void calcOpt() {
	for (int i = 1; i <= n; ++i) {
		for (auto j : G[i]) deg[j]++;
	} 
	queue<int> qu;
	for (int i = 1; i <= n; ++i) {
		if (!deg[i]) qu.push(i);
		opt[i].push_back(make_pair(0, i));
	}
	while (qu.size()) {
		int u = qu.front(); qu.pop();
		for (auto &i : opt[u]) i.first++;
		for (auto v : G[u]) {
			Merge(opt[v], opt[u]);
			deg[v]--; if (!deg[v]) qu.push(v);
		}
		for (auto &i : opt[u]) i.first--;
	}
}

void bfs(int pos) {
	for (int i = 1; i <= n; ++i) {
		if (!vis[i]) dis[i] = 0; else dis[i] = -INF;
		for (auto j : G[i]) deg[j]++;
	}
	queue<int> qu;
	for (int i = 1; i <= n; ++i) {
		if (!deg[i]) qu.push(i);
	}
	while (qu.size()) {
		int u = qu.front(); qu.pop();
		for (auto v : G[u]) {
			dis[v] = max(dis[v], dis[u] + 1);
			deg[v]--; if (!deg[v]) qu.push(v);
		}
	}
	res = dis[pos];
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m >> q;
	for (int i = 1; i <= m; ++i) {
		int u, v; cin >> u >> v;
		G[u].push_back(v);
	}
	calcOpt();
	// for (int i = 1; i <= n; ++i) {
	// 	cout << "#at " << i << '\n';
	// 	for (auto j : opt[i]) cout << j.first << ' ' << j.second << '\n';
	// }
	for (int i = 1; i <= q; ++i) {
		int pos; cin >> pos;
		int sz; cin >> sz;
		buf.clear();
		for (int j = 1; j <= sz; ++j) {
			int x; cin >> x, buf.push_back(x), vis[x] = 1;
		}
		res = -INF;
		if (sz < M) {
			for (auto j : opt[pos]) {
				if (!vis[j.second]) {
					res = j.first; break;
				}
			}
		}
		else bfs(pos);
		for (auto j : buf) vis[j] = 0;
		cout << (res < 0 ? -1 : res) << '\n';
	}
}

Compilation message (stderr)

bitaro.cpp: In function 'void Merge(std::vector<std::pair<int, int> >&, std::vector<std::pair<int, int> >&)':
bitaro.cpp:34:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (A < a.size() && B < b.size()) {
         ~~^~~~~~~~~~
bitaro.cpp:34:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (A < a.size() && B < b.size()) {
                         ~~^~~~~~~~~~
bitaro.cpp:38:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (A < a.size()) add(a, A);
         ~~^~~~~~~~~~
bitaro.cpp:39:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (B < b.size()) add(b, B);
         ~~^~~~~~~~~~

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