Submission #923440

#	Time	Username	Problem	Language	Result	Execution time	Memory
923440		hqminhuwu	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1448 ms	414648 KiB

bitaro

#include <bits/stdc++.h>
#define forr(_a,_b,_c) for(_a = (_b); _a <= (_c); ++_a)
#define ford(_a,_b,_c) for(_a = (_b) + 1; _a --> (_c);)
#define forf(_a,_b,_c) for(_a = (_b); _a < (_c); ++_a)
#define st first
#define nd second
#define ll long long
#define ull unsigned long long
#define pii pair <int,int>
#define pll pair <ll,ll>
#define piii pair <int,pii>
#define vi vector <int>
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define file "test"


using namespace std;
const int N = 1e5 + 5;
const ll oo = 1e9;
const ll mod = 1e9 + 7;

int pv = sqrt(100000), dp[N], w[N], u, v, k, m, n, q, i, e[N], x, mx[N];
vi a[N], tmp;
vector <pii> f[N];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	#ifdef hqm
	   freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
	#endif

	cin >> n >> m >> q;
	
	forr (i, 1, m){
		cin >> u >> v;
		a[v].pb(u);
	}

	forr (i, 1, n){
		f[i].pb({0, i});
		for (int v : a[i]){
			for (pii u : f[v]){
				if (!mx[u.nd])
                	tmp.pb(u.nd);
                mx[u.nd] = max (mx[u.nd], u.st + 1);
            }
		}
		for (int u : tmp)
			f[i].pb({mx[u], u}), mx[u] = 0;
		tmp.clear();
		sort(all(f[i]), greater<pii>());
		while (f[i].size() > pv)
			f[i].pop_back();
		
	}

	while (q--){
		cin >> x;
		cin >> k;
		forr (i, 1, k){
			cin >> e[i];
			w[e[i]] = 1;
		}

		int ans = -1;

		if (k < pv){
			for (pii u : f[x]){
				if (!w[u.nd]){
					ans = u.st;
					break;
				}
			}
		}
		else {
			forr (i, 1, x){
				if (!w[i])
					dp[i] = 0;
				else dp[i] = -oo;
				for (int v : a[i])
					dp[i] = max (dp[i], dp[v] + 1);
			}
			if (dp[x] >= 0)
				ans = dp[x];
		}
		cout << ans << "\n";
		forr (i, 1, k)
			w[e[i]] = 0;
	}
	return 0;
}
/*



*/

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:54:22: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |   while (f[i].size() > pv)
      |          ~~~~~~~~~~~~^~~~

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