Submission #95041

#	Time	Username	Problem	Language	Result	Execution time	Memory
95041		Mahdi_Jfri	Bitaro’s Party (JOI18_bitaro)	C++14	14 / 100	1170 ms	480248 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
typedef vector<pair<int,int>> vii;

const int maxn = 1e5 + 20;
const int sq = 320;

vector<int> in[maxn];
vii path[maxn];

int dp[maxn];

bool is[maxn];

bool cmp(pair<int , int> a , pair<int , int> b)
{
	return a > b;
}

void merge(vii &a , vii &b)
{
	vii c(a.size() + b.size());
	merge(a.begin() , a.end() , b.begin() , b.end() , c.begin() , cmp);
	a = c;

	while(a.size() > sq)
		a.pop_back();
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.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--;
		in[b].pb(a);
	}

	for(int v = 0; v < n; v++)
	{
		path[v].pb({-1 , v});
		for(auto u : in[v])
			merge(path[v] , path[u]);

		for(auto &x : path[v])
			x.first++;
	}

	while(q--)
	{
		int v , sz;
		cin >> v >> sz;
		v--;

		vector<int> tmp(sz);
		for(auto &x : tmp)
			cin >> x , x--;

		for(auto x : tmp)
			is[x] = 1;

		if(sz > sq)
		{
			for(int i = 0; i <= v; i++)
			{
				dp[i] = -1e9;
				if(!is[i])
					dp[i] = 0;
				for(auto u : in[i])
					dp[i] = max(dp[i] , dp[u] + 1);
			}

			dp[v] = max(dp[v] , -1);
			cout << dp[v] << endl;
		}
		else
		{
			bool f = 0;
			for(auto x : path[v])
				if(!is[x.second])
				{
					cout << x.first << endl;
					f = 1;
					break;
				}

			if(!f)
				cout << -1 << endl;
		}

		for(auto x : tmp)
			is[x] = 0;
	}
}

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