Submission #51857

#	Time	Username	Problem	Language	Result	Execution time	Memory
51857		shoemakerjo	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1820 ms	242352 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;

#define maxn 100010
#define endl '\n'

const int block = 300;
const int inf = 1234567890;

int bestval[maxn][block]; //all 0's is good 
int bestdist[maxn][block]; //starts at all 0's which is good
int ndist[block];
int nval[block];

int bd[maxn]; //used for things that are greater than square root n
int bv[maxn];

bool cseen[maxn]; //used during the merge thing
bool illegal[maxn]; //used for queries greater than maxn
int N, M, Q;

vector<vector<int>> adj(maxn);

void merge(int x, int y) {
	// cout << "merging: " << x << " into " << y << endl;
	//merge everything from y into x (going to y will increase distance by 1)
	int ind = -1;
	int p1 = 0;
	int p2 = 0;
	while (++ind < block) { //run a merge-sort like algorithm
		// cout << ind << " - " << block << endl;
		cseen[0] = false;
		while (cseen[bestval[x][p1]]) ++p1;
		while (cseen[bestval[y][p2]]) ++p2;
		if (bestdist[x][p1] > bestdist[y][p2]+1) {
			ndist[ind] = bestdist[x][p1];
			nval[ind] = bestval[x][p1];
			p1++;
			cseen[nval[ind]] = true;
		}
		else {
			ndist[ind] = bestdist[y][p2]+1;
			nval[ind] = bestval[y][p2];
			p2++;
			cseen[nval[ind]] = true;
		}
	}
	for (int i = 0; i < block; i++) {
		bestval[x][i] = nval[i];
		bestdist[x][i] = ndist[i];
		cseen[nval[i]] = false; //unmark it for the next iteration
	}
}


void recalculate() {
	for (int i = 1; i <= N; i++) {
		bd[i] = 0;
		if (!illegal[i]) {
			bv[i] = i;
		}
		else {
			bv[i] = 0;
			bd[i] = -inf;
		}
		for (int val : adj[i]) {
			if (bd[val] + 1 > bd[i]) {
				bd[i] = bd[val]+1;
				bv[i] = bv[val]; //don't think i actually need this but maybe
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> M >> Q;
	int ti; //party location in the query
	int yi; //used for queries
	int s, e; //used for edges
	for (int i = 0; i < M; i++) {
		cin >> s >> e; //reverse edges here
		adj[e].push_back(s);
	}

	//process from back to front
	for (int i = 1; i <= N; i++) {
		// cout << "at: " << i << endl;
		//want what can get to this (or what this gets to in reversed graph)
		fill(bestdist[i], bestdist[i]+block, -inf);

		//calculate everything for this
		bestval[i][0] = i; //store myself
		bestdist[i][0] = 0;
		for (int val : adj[i]) {
			merge(i, val);
		}
		// cout << "best dist for " << i << ": " << bestdist[i][0] << endl;

	}
	int cur;
	while (Q--) {
		// cout << "here:  " << Q << endl;
		cin >> ti >> yi;
		vector<int> cl; //current illegal
		for (int i = 0; i < yi; i++) {
			cin >> cur;
			cl.push_back(cur);
			illegal[cur] = true;
		}
		//do processing
		if (yi < block) {
			//do first thing
			int ind = 0;
			while (illegal[bestval[ti][ind]]) {
				// cout << ind << ": " << bestval[ti][ind] << endl;
				ind++;
			}
			// cout << ind << ": " << bestval[ti][ind] << endl;
			if (bestval[ti][ind] != 0 && bestdist[ti][ind] >= 0) {
				cout << bestdist[ti][ind] << endl;
			}
			else cout << -1 << endl;
		}
		else {
			recalculate();
			if (bv[ti] != 0 && bd[ti] >= 0) {
				cout << bd[ti] << endl; 
				//we just want the distance, not the index
			}
			else cout << -1 << endl;
		}
		//mark the things as ok again
		for (int i = 0; i < yi; i++) {
			illegal[cl[i]] = false;
		}
	}
	cout.flush();
	cin >> N;

}

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