제출 #1112106

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1112106		Muaath_5	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	2066 ms	56744 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)

#pragma GCC optimize("Ofast,O3")
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;

const int N = 1e5+1, SQ = 350;

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

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

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

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin >> n >> m >> q;
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		adj[v].push_back(u);
	}
	
	// precalc
	for (int i = 1; i <= n; i++) {
		len[i] = 1;
		dp[i][0] = {0, i};
		// cerr << "---\n";
		for (int j : adj[i]) {
			// cerr << "A: ";
			// for (auto [x, y] : dp[i])
				// cerr << x << ',' << y << ' ';
			// cerr<<endl;
// 			
			// cerr << "B: ";
			// for (auto [x, y] : dp[j])
				// cerr << x << ',' << y << ' ';
			// cerr<<endl;
			vector<pii> res;
			res.reserve(SQ);
			int p1 = 0, p2 = 0;
			while (p1 < len[i] && p2 < len[j]) {
				if (dp[i][p1] == pii{dp[j][p2].first+1, dp[j][p2].second})
					p1++;
				else if (dp[i][p1].first > dp[j][p2].first+1)
					res.push_back(dp[i][p1++]);
				else {
					res.push_back({dp[j][p2].first+1, dp[j][p2].second});
					p2++;
				}
			}
			while (p1 < len[i] && res.size() < SQ)
				res.push_back(dp[i][p1++]);
			while (p2 < len[j] && res.size() < SQ) {
				res.push_back({dp[j][p2].first+1, dp[j][p2].second});
				p2++;
			}
			
			len[i] = res.size();
			for (int x = 0; x < len[i]; x++)
				dp[i][x] = res[x];
		}
	}
	
	while (q--) {
		int t, y;
		cin >> t >> y;
		
		vector<int> c(y);
		for (int &i : c) {
			cin >> i;
			mp[i] = 1;
		}
		
		if (y >= SQ) {
			for (int i = 1; i <= n; i++) {
				for (int prv : adj[i]) {
					if (!mp[prv] || dp2[prv] > 0)
						dp2[i] = max(dp2[i], dp2[prv]+1);
				}
			}
			cout << (dp2[t] == 0 && mp[t] ? -1 : dp2[t]) << '\n';
		} else {
			bool ok = false;
			for (int i = 0; i < len[t]; i++) {
				if (!mp[dp[t][i].second]) {
					cout << dp[t][i].first << '\n';
					ok = true;
					break;
				}
			}
			if (!ok)
				cout << "-1\n";
		}
		for (int &i : c) {
			mp[i] = 0;
		}
	}
}

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