Submission #482133

#	Time	Username	Problem	Language	Result	Execution time	Memory
482133		ymm	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	878 ms	256728 KiB

bitaro

///
///   NOW'S YOUR CHANCE TO BE A [[BIG SHOT]]!!
///

#include <bits/stdc++.h>
typedef long long ll;
typedef std::pair<int,int> pii;
#define F first
#define S second
using namespace std;

const int N = 100010;
static const int S = 310;
typedef vector<pii> vec;

vector<int> A[N];
int n, m;
bitset<N> busy;
vec dard[N];
int ans[N];

void mymerge(vec& a, vec& b)
{
	static bitset<N> has; has.reset();
	static vec ans(S);
	int p1=0, p2=0;
	for(int i = 0; i < S;)
	{
		has[N-1] = 0;
		if(a[p1].F >= b[p2].F+1)
		{
			if(!has[a[p1].S]){
				has[a[p1].S] = 1;
				ans[i] = a[p1];
				++i;
			}
			++p1;
		} else {
			if(!has[b[p2].S]){
				has[b[p2].S] = 1;
				ans[i] = {b[p2].F+1, b[p2].S};
				++i;
			}
			++p2;
		}
	}
	a.swap(ans);
}

void Do1()
{
	for(int v = 0; v < n; ++v)
	{
		dard[v] = vec(S, pii{-N, N-1});
		dard[v][0] = {0, v};
		for(int u : A[v])
			mymerge(dard[v], dard[u]);
	}
}

void Do2()
{
	for(int v = 0; v < n; ++v)
	{
		ans[v] = busy[v]?-N:0;
		for(int u : A[v])
			ans[v] = max(ans[v], ans[u]+1);
	}
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
	int q;
	cin >> n >> m >> q;
	for(int i = 0; i < m; ++i)
	{
		int s, t;
		cin >> s >> t;
		A[t-1].push_back(s-1);
	}
	Do1();
	while(q--)
	{
		int t, y;
		cin >> t >> y; --t;
		vector<int> kooft(y);
		for(int i = 0; i < y; ++i)
			cin >> kooft[i],
			busy[kooft[i]-1] = 1;
		if(y < S)
		{
			int ans = 0;
			while(busy[dard[t][ans].S])
				++ans;
			cout << (dard[t][ans].S == N-1? -1: dard[t][ans].F) << '\n';
		}
		else
		{
			Do2();
			cout << (ans[t]<0?-1:ans[t]) << '\n';
		}
		for(int i = 0; i < y; ++i)
			busy[kooft[i]-1] = 0;
	}
}

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