Submission #1113230

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113230		Muaath_5	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1460 ms	244808 KiB

bitaro

// Problem: C - Bitaro's Party
// Contest: Virtual Judge - Square root tech
// URL: https://vjudge.net/contest/671583#problem/C
// Memory Limit: 507 MB
// Time Limit: 2000 ms
// 
// By Muaath Alqarni
// Blog: https://muaath5.githib.io/blog
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;

const int N = 1e5+5, SQ = 300;

int n, m, q;
vector<int> adj[N];

int len[N];
pair<int, int> dp[N][SQ];

char mp[N];
int dp2[N];

static inline int read()
{
    int x = 0;char ch = getchar();
    while (ch < '0' || ch>'9') ch = getchar();
    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
    return x;
}

static inline void print(const int &x) {
    if (x > 9)print(x / 10);
    putchar('0' + x % 10);
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	n=read(),m=read(),q=read();
	for (int i = 0; i < m; i++) {
		int u=read(), v=read();
		adj[v].push_back(u);
	}
	
	// precalc
	vector<pii> res;
	res.reserve(SQ);
	vector<bool> used(n+1, 0);
	for (int i = 1; i <= n; i++) {
		len[i] = 1;
		dp[i][0] = {0, i};
		for (int j : adj[i]) {
			res.clear();
			int p1 = 0, p2 = 0;
			while (res.size() < SQ && p1 < len[i] && p2 < len[j]) {
				if (used[dp[i][p1].second]) {
					p1++;
					continue;
				}
				if (used[dp[j][p2].second]) {
					p2++;
					continue;
				}
					
				if (dp[i][p1].first > dp[j][p2].first+1)
					used[dp[i][p1].second] = 1, res.push_back(dp[i][p1++]);
				else {
					used[dp[j][p2].second] = 1;
					res.push_back({dp[j][p2].first+1, dp[j][p2].second});
					p2++;
				}
			}
			while (p1 < len[i] && res.size() < SQ) {
				if (!used[dp[i][p1].second])
					used[dp[i][p1].second] = 1, res.push_back(dp[i][p1]);
				p1++;	
			}
				
			while (p2 < len[j] && res.size() < SQ) {
				if (!used[dp[j][p2].second])
					used[dp[j][p2].second] = 1, res.push_back({dp[j][p2].first+1, dp[j][p2].second});
				p2++;	
			}
		
			
		
			if (res.size() > SQ)
				res.resize(SQ);
			sort(res.begin(), res.end(), greater<>());
			len[i] = res.size();
			for (int x = 0; x < len[i]; x++) {
				used[res[x].second] = false;
				dp[i][x] = res[x];
			}
		}
	}
	
	while (q--) {
		int t=read(), y=read();
		
		vector<int> c(y);
		for (int &i : c) {
			i=read();
			mp[i] = 1;
		}
		

		if (y < SQ) {
			bool ok = false;
			for (int i = 0; i < len[t]; i++) {
				if (!mp[dp[t][i].second]) {
					print(dp[t][i].first);
					ok = true;
					break;
				}
			}
			if (!ok)
				putchar('-'),putchar('1');
		}
		else {
			for (int i = 1; i <= t; i++) {
				dp2[i] = 0;
				for (int prv : adj[i]) {
					if (!mp[prv] || dp2[prv] > 0)
						dp2[i] = max(dp2[i], dp2[prv]+1);
				}
			}
			if (dp2[t] == 0 && mp[t])
				putchar('-'),putchar('1');
			else
				print(dp2[t]);
		} 
		putchar('\n');
		for (int &i : c) {
			mp[i] = 0;
		}
	}
}

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