Submission #627111

#	Time	Username	Problem	Language	Result	Execution time	Memory
627111		pooyashams	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	774 ms	170796 KiB

bitaro

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <iomanip>
#include <vector>
#include <bitset>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define endl '\n'
#define X first
#define Y second

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const int maxn = 2e5+10;
const int sq = 202;
const int inf = 1e9;

pii dst[maxn][sq];
vector<int> G[maxn];

pii tmp[sq*2+1];
bool _vis[maxn+1];
bool *vis = _vis+1;

inline void mrg(int a, int b) // a < b
{
	int pa = 0;
	int pb = 0;
	while(pa < sq or pb < sq)
	{
		if(pa == sq or (pb < sq and dst[b][pb].X > dst[a][pa].X+1) )
		{
			tmp[pa+pb] = dst[b][pb];
			pb++;
		}
		else
		{
			tmp[pa+pb] = dst[a][pa];
			tmp[pa+pb].X++;
			pa++;
		}
	}
	int c = 0;
	for(int i = 0; i < sq+sq and c < sq; i++)
	{
		if(tmp[i].Y != -1 and !vis[tmp[i].Y])
		{
			vis[tmp[i].Y] = true;
			dst[b][c++] = tmp[i];
		}
	}
	for(int i = 0; i < sq+sq; i++)
		if(tmp[i].Y != -1)
			vis[tmp[i].Y] = false;
}

bool dead[maxn];

int dtmp[maxn];

int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m, q; cin >> n >> m >> q;
	for(int i = 0; i < m; i++)
	{
		int a, b; cin >> a >> b;
		a--; b--;
		G[b].push_back(a);
	}
	for(int i = 0; i < n; i++)
	{
		fill(dst[i], dst[i]+sq, pii(-1, -1));
		dst[i][0] = pii(0, i);
		for(int j: G[i])
			mrg(j, i);
	}
	while(q--)
	{
		int t, k; cin >> t >> k;
		t--;
		vector<int> dd(k);
		for(int i = 0; i < k; i++)
		{
			cin >> dd[i];
			dd[i]--;
			dead[dd[i]] = true;
		}
		int ans = -1;
		if(k < sq)
		{
			for(int i = 0; i < sq; i++)
				if(!dead[dst[t][i].Y])
					ans = max(ans, dst[t][i].X);
		}
		else
		{
			for(int i = 0; i <= t; i++)
			{
				if(dead[i])
					dtmp[i] = -1;
				else
					dtmp[i] = 0;
				for(int j: G[i])
				{
					if(dtmp[j] != -1)
						dtmp[i] = max(dtmp[i], dtmp[j]+1);
				}
			}
			ans = dtmp[t];
		}
		cout << ans << endl;
		for(int x: dd)
			dead[x] = false;
	}
	return 0;
}

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