Submission #164021

#TimeUsernameProblemLanguageResultExecution timeMemory
164021oolimryBitaro’s Party (JOI18_bitaro)C++14
0 / 100
13 ms9976 KiB
#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> ii;
typedef vector<int> vi;

struct query{
	int id;
	unordered_set<int> cannot;
};
static set<ii, greater<ii> > dp[100005];
static int offset[100005]; ///dp[i] + offset[i] = actual value
static vi adj[100005];
static int answer[100005];
static vector<query> queries[100005];
int main(){
	//freopen("i.txt","r",stdin);
	ios_base::sync_with_stdio(false);
	cin.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--;
		adj[b].push_back(a);
	}
	
	for(int qq = 0;qq < q;qq++){
		int y, t;
		cin >> y >> t;
		y--;
		query nQ;
		nQ.id = qq;
		for(int i = 0;i < t;i++){
			int x;
			cin >> x;
			x--;
			nQ.cannot.insert(x);
		}
		queries[y].push_back(nQ);
	}
	
	for(int u = 0;u < n;u++){
		dp[u].insert(ii(0,u));
		
		for(int v : adj[u]){
			if(dp[u].size() >= dp[v].size()){
				for(ii x : dp[v]){
					dp[u].insert(ii(x.first+1+offset[v]-offset[u],x.second));
				}
			}
			else{
				swap(dp[u],dp[v]);
				swap(offset[u],offset[v]);
				offset[u]++;
				offset[v]--;
				for(ii x : dp[v]){
					dp[u].insert(ii(x.first+1+offset[v]-offset[u],x.second));
				}
			}
		}
		
		for(query qq : queries[u]){
			bool can = false;
			for(ii x : dp[u]){
				if(qq.cannot.find(x.second) == qq.cannot.end()){
					answer[qq.id] = x.first + offset[u];
					can = true;
					break;
				}
			}
			if(!can) answer[qq.id] = -1;
		}
		/*
		for(ii x : dp[u]){
			cout << "(" << x.first + offset[u] << ", " << x.second << ") ";
		}
		cout << offset[u] << "\n";
		//*/
	}
	
	for(int i = 0;i < q;i++){
		cout << answer[i] << "\n";
	}
	
	
	
	
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...