Submission #599686

#	Time	Username	Problem	Language	Result	Execution time	Memory
599686		GusterGoose27	Bitaro’s Party (JOI18_bitaro)	C++11	100 / 100	870 ms	81048 KiB

bitaro

#pragma GCC optimize("O3")
#pragma GCC target("avx2")

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 1e5;
const int MAXrtn = 90;
int n, m, q;
bool inactive[MAXN];
pii precomp[MAXN][MAXrtn]; // dist, node
int rtn = 90;
vector<int> edges[MAXN];
int dp[MAXN];
int posses[MAXN];
bool vis[MAXN];

void make() {
	for (int i = 0; i < n; i++) {
		fill(precomp[i], precomp[i]+rtn, pii(-1, -1));
		priority_queue<pii> pq; // push the index where it came from not the original index
		pq.push(pii(0, i));
		for (int in: edges[i]) {
			posses[in] = 0;
			pq.push(pii(precomp[in][0].first+1, in));
		}
		for (int t = 0; !pq.empty() && t < rtn; t++) {
			pii top = pq.top();
			pq.pop();
			int cnode = top.second;
			if (top.first == -1) break;
			if (cnode == i) {
				precomp[i][t] = top;
				break;
			}
			if (!vis[precomp[cnode][posses[cnode]].second]) {
				precomp[i][t] = pii(top.first, precomp[cnode][posses[cnode]].second);
				vis[precomp[cnode][posses[cnode]].second] = 1;
			}
			else {
				t--;
			}
			posses[cnode]++;
			if (posses[cnode] < rtn && precomp[cnode][posses[cnode]].first >= 0) pq.push(pii(precomp[cnode][posses[cnode]].first+1, cnode));
		}
		for (int t = 0; t < rtn; t++) if (precomp[i][t].second != -1) vis[precomp[i][t].second] = 0;
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> m >> q;
	for (int i = 0; i < m; i++) {
		int x, y; cin >> x >> y; x--; y--;
		if (y < x) {
			int temp = x; x = y; y = temp;
		}
		edges[y].push_back(x);
	}
	//rtn = max(1, (int) (sqrt(n)/15));
	make();
	for (int t = 0; t < q; t++) {
		int pos, num;
		cin >> pos >> num;
		pos--;
		if (num >= rtn) {
			memset(inactive, 0, sizeof(bool)*n);
			for (int i = 0; i < num; i++) {
				int x; cin >> x; x--;
				inactive[x] = 1;
			}	
			for (int i = 0; i <= pos; i++) {
				if (inactive[i]) {
					dp[i] = -1;
				}
				else dp[i] = 0;
				for (int in: edges[i]) {
					if (dp[in] >= 0) dp[i] = max(dp[i], 1+dp[in]);
				}
			}
			cout << dp[pos] << "\n";
			continue;
		}
		vector<int> v;
			for (int i = 0; i < num; i++) {
			int x; cin >> x; x--;
			vis[x] = 1;
			v.push_back(x);
		}
		for (int i = 0; i < rtn; i++) {
			if (!vis[precomp[pos][i].second]) {
				cout << precomp[pos][i].first << "\n";
				break;
			}
		}
		for (int rv: v) vis[rv] = 0;
		//assert(false);
	}
}

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