제출 #1234264

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1234264		hashdfdfh	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	894 ms	216368 KiB

bitaro

#include <bits/stdc++.h>
#define mid ((l+r)>>1)
using namespace std;
vector<int> vc[200005];
vector<pair<int, int>> nr[200005];
int B = 150;
int ok[200005], dist[200005], tag[200005];
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int n, m, q; cin >> n >> m >> q;
	for (int i = 1; i <= m; i++) {
		int u, v; cin >> u >> v;
		vc[u].push_back(v);
	}
	for (int i = 1; i <= n; i++) {
		if (nr[i].size() < B) {
			nr[i].push_back(make_pair(0, i));
		}
		for (auto v : vc[i]) {
			vector<pair<int, int>> nw;
			int it1 = 0, it2 = 0;
			while (((it1 != nr[i].size()) || (it2 != nr[v].size())) && (nw.size() < B)) {
				if (it1 == nr[i].size()) {
					if (tag[nr[v][it2].second]) {
						it2++;
						continue;
					}  tag[nr[v][it2].second] = 1;
					nw.push_back(nr[v][it2]);
					it2++;
					continue;
				}
				if (it2 == nr[v].size()) {
					if (tag[nr[i][it1].second]) {
						it1++;
						continue;
					} tag[nr[i][it1].second] = 1;
					auto t = nr[i][it1];
					t.first++;
					nw.push_back(t);
					it1++;
					continue;
				}
				if (nr[i][it1].first + 1 > nr[v][it2].first) {
					if (tag[nr[i][it1].second]) {
						it1++;
						continue;
					} tag[nr[i][it1].second] = 1;
					auto t = nr[i][it1];
					t.first++;
					nw.push_back(t);
					it1++;
					continue;
				}
				else {
					if (tag[nr[v][it2].second]) {
						it2++;
						continue;
					} tag[nr[v][it2].second] = 1;
					nw.push_back(nr[v][it2]);
					it2++;
					continue;
				}
			}
			swap(nw, nr[v]);
			nw.clear();
			for (auto u : nr[v]) tag[u.second] = 0;
		}
	}
	//	for(int i=1;i<=n;i++,cout<<"\n") for(auto v:nr[i]) cout<<v.first<<" "<<v.second<<"  ";
	while (q--) {
		int s, k; cin >> s >> k;
		if (k >= 150) {
			for (int i = 1; i <= n; i++) ok[i] = 1, dist[i] = -1;
			while (k--) {
				int x; cin >> x; ok[x] = 0;
			}
			for (int i = 1; i <= n; i++) {
				if (ok[i]) dist[i] = max(dist[i], 0);
				if (dist[i] >= 0) {
					for (auto v : vc[i]) {
						dist[v] = max(dist[v], dist[i] + 1);
					}
				}
			}
			cout << dist[s] << "\n";
		}
		else {
			vector<int> nd;
			while (k--) {
				int x; cin >> x; nd.push_back(x);
			}
			for (auto v : nd) tag[v] = 1;
			int maxv = -1;
			for (auto v : nr[s]) {
				if (!tag[v.second]) {
					maxv = v.first;
					break;
				}
			}
			for (auto v : nd) tag[v] = 0;
			cout << maxv << "\n";
		}
	}
	return 0;
}

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