Submission #735652

#	Time	Username	Problem	Language	Result	Execution time	Memory
735652		Mister_HDS	Bitaro’s Party (JOI18_bitaro)	C++14	14 / 100	2086 ms	119272 KiB

bitaro

#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
#define IOS                       \
	ios_base::sync_with_stdio(0); \
	cin.tie(0);                   \
	cout.tie(0);
using namespace std;
const ll MOD = 1e9 + 7;
const double EPS = 1e-7;
const int MAX = (int)1e5 + 10;
const double PI = acos(-1);

vector<int> adj[MAX];
vector<int> par[MAX];

vector<pair<int, int>> shits[MAX];
int frq[MAX];

bool removed[MAX];
int sqrt_n = 80;

void build(queue<int> q, vector<int> ind)
{
	while (!q.empty())
	{
		int curNode = q.front();
		q.pop();

		for (auto node : adj[curNode])
		{
			ind[node]--;
			if (ind[node] == 0)
				q.push(node);
		}

		vector<pair<int, int>> &res = shits[curNode];
		res.push_back({0, curNode});
		for (auto node : par[curNode])
		{
			for (auto x : shits[node])
			{
				frq[x.second] = max(frq[x.second], x.first + 1);
			}
		}
		for (auto node : par[curNode])
		{
			for (auto x : shits[node])
			{
				if (frq[x.second] > 0)
				{
					res.push_back({frq[x.second], x.second});
					frq[x.second] = 0;
				}
			}
		}
		sort(res.rbegin(), res.rend());
		while ((int)res.size() > sqrt_n)
		{
			res.pop_back();
		}
		// cout << curNode << endl;
		// for(auto x : res) cout << x.first << " " << x.second << endl ;
	}
}

int bfs(queue<int> q, vector<int> ind, int n, int nodeParty)
{
	vector<int> dis(n + 1, 0);
	while (!q.empty())
	{
		int curNode = q.front();
		q.pop();
		for (auto node : adj[curNode])
		{
			ind[node]--;
			if (ind[node] == 0)
				q.push(node);
			if (dis[curNode] == 0 && removed[curNode] == true)
				continue;
			dis[node] = max(dis[node], dis[curNode] + 1);
		}
	}
	return dis[nodeParty];
}

void solve()
{
	int n, m, q;
	cin >> n >> m >> q;
	vector<int> ind(n + 1, 0);
	for (int i = 0; i < m; i++)
	{
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		par[v].push_back(u);
		ind[v]++;
	}
	queue<int> roots;
	for (int i = 1; i <= n; i++)
	{
		if (ind[i] == 0)
			roots.push(i);
	}

	build(roots, ind);

	while (q--)
	{
		int nodeParty, totalRemoved;
		vector<int> rmv;
		cin >> nodeParty >> totalRemoved;
		for (int i = 1; i <= totalRemoved; i++)
		{
			int node;
			cin >> node;
			rmv.push_back(node);
		}
		for (auto node : rmv)
			removed[node] = true;

		int sz = (int)rmv.size();
		int ans = -1;
		if (sz > sqrt_n)
		{ // FIRST TYPE OF QUESRIES
			ans = bfs(roots, ind, n, nodeParty);
		}
		else
		{
			for (auto node : shits[nodeParty])
			{
				if (removed[node.second] == false)
				{
					ans = max(ans, node.first);
				}
			}
		}
		if (ans == 0 && removed[nodeParty] == true)
			ans = -1;
		cout << ans << endl;
		for (auto node : rmv)
			removed[node] = false;
	}
}
int main()
{
	IOS;
	solve();

	return 0;
}

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