제출 #1308789

#제출 시각아이디문제언어결과실행 시간메모리
1308789sagsterBitaro’s Party (JOI18_bitaro)C++20
14 / 100
260 ms13632 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 100010, B = 300;

vector<pair<int,int>> merge(vector<pair<int,int>> &tobe, vector<pair<int,int>> &merged){
	vector<pair<int,int>> res;
	map<int,int> jafoi;
	int p1 = 0, p2 = 0, size1 = tobe.size(), size2 = merged.size(), ct = 0;
	while(ct < B && (p1 < size1 || p2 < size2)){
		if(p2 == size2){
			// cout << "1 " << p1 << " " << p2 << endl;
			if(!jafoi.count(tobe[p1].second)){
				jafoi[tobe[p1].second]++;
				res.push_back(tobe[p1]);
				ct++;
				// cout << "ebaaa1 " << res[res.size()-1].first << " " << res[res.size()-1].second << endl;
			}	
			p1++;
		}
		else if(p1 == size1){
			// cout << "2 " << p1 << " " << p2 << endl;
			if(!jafoi.count(merged[p2].second)){
				jafoi[merged[p2].second]++;
				res.push_back({merged[p2].first + 1, merged[p2].second});
				ct++;
				// cout << "ebaaa2 " << res[res.size()-1].first << " " << res[res.size()-1].second << endl;
			}	
			p2++;
		}
		else if(tobe[p1].first > merged[p2].first + 1){
			// cout << "3 " << p1 << " " << p2 << endl;
			if(!jafoi.count(tobe[p1].second)){
				jafoi[tobe[p1].second]++;
				res.push_back(tobe[p1]);
				ct++;
				// cout << "ebaaa3 " << res[res.size()-1].first << " " << res[res.size()-1].second << endl;
			}	
			p1++;
		}
		else{
			// cout << "4 " << p1 << " " << p2 << endl;
			if(!jafoi.count(merged[p2].second)){
				jafoi[merged[p2].second]++;
				res.push_back({merged[p2].first + 1, merged[p2].second});
				ct++;
				// cout << "ebaaa4 " << res[res.size()-1].first << " " << res[res.size()-1].second << endl;
			}	
			p2++;
		}
	}
	return res;
}

signed main(){
	int n, m, q; cin >> n >> m >> q;
	vector<vector<int>> nei(n, vector<int>(0)); // .f = dist ,,, .s = id
	for(int i = 0; i < m; i++){
		int a, b; cin >> a >> b;
		nei[a-1].push_back(b-1);
	}
	vector<vector<pair<int,int>>> dist(n, vector<pair<int,int>>(0));
	for(int i = 0; i < n; i++) dist[i].push_back({(int)0,i});
	// for(int i = 0; i < n; i++){
	// 	for(auto v : nei[i]){
	// 		dist[v] = merge(dist[v], dist[i]);
	// 	}
	// }

	// for(int i = 0; i < n; i++){
	// 	cout << i+1 << ":\n";
	// 	for(auto [distance, frie] : dist[i]){
	// 		cout << distance << " " << frie+1 << endl;
	// 	}
	// 	cout << "\n\n";
	// }
	for(int i = 0; i < q; i++){
		int cid, bloq; cin >> cid >> bloq;
		cid--;
		vector<bool> block(N);
		for(int j = 0; j < bloq;j++){
			int x; cin >> x;
			block[x-1] = true;
		}
		// cout << "\n\noioi";
		// for(int j = 0; j < n; j++) cout << block[j] << endl;
		// cout << "\n\n";

		if(bloq >= B){
			vector<pair<int,int>> maior(n);
			for(int j = 0; j < n; j++) maior[j] = {0,j};
			for(int j = 0; j < cid; j++){
				for(auto cur : nei[j]){
					if(!block[maior[j].second] && maior[j].first + 1 > maior[cur].first){
						maior[cur] = {maior[j].first + 1, maior[j].second};
						// cout << j+1<< " atualizando " << cur+1 << "  " << maior[cur].first << " "<< maior[cur].second+1 << "\n";
					}
				}
			}
			if(!block[maior[cid].second]) cout << maior[cid].first << "\n";
			else cout << -1 << "\n";
		}
		else{
			// cout << cid+1 << " " << bloq << "   ";
			bool a = true;
			for(auto [distance, frie] : dist[cid]){
				if(!block[frie]){
					cout << distance << endl;
					a = false;
					break;
				}
			}
			if(a) cout << -1 << endl;
		}
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...