Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Testando o código do pauloamed
- #include<bits/stdc++.h>
- using namespace std;
- #define MAXN 100010
- #define MAXK 100
- #define ppiii pair<pair<int,int>,int>
- int n;
- vector<int> v[MAXN];
- vector<int> rv[MAXN];
- int pd[MAXN];
- int fullSolution(int x, vector<bool> &on){
- memset(pd, -1, sizeof(pd));
- int ans = -1;
- pd[x] = 0;
- for(int i = x; i >= 0; --i){
- if(pd[i] != -1){
- for(auto y : rv[i]){
- pd[y] = max(pd[y], pd[i] + 1);
- }
- }
- if(on[i]) ans = max(ans, pd[i]);
- }
- return ans;
- }
- int main(){
- int m, q; scanf("%d %d %d", &n, &m, &q);
- for(int i = 0; i < m; ++i){
- int a, b; scanf("%d %d", &a, &b);; a--, b--;
- if(a > b) swap(a, b);
- v[a].push_back(b);
- rv[b].push_back(a);
- }
- // cout << block << endl;
- vector<vector<pair<int,int>>> bestDists(n);
- vector<bool> occour(n);
- for(int i = 0; i < n; ++i){
- vector<int> currPointers(rv[i].size());
- priority_queue<ppiii, vector<ppiii>, less<ppiii>> pq;
- for(int j = 0; j < rv[i].size(); ++j){
- pq.push(make_pair(bestDists[rv[i][j]].front(), j));
- }
- while(pq.size() && bestDists[i].size() < MAXK){
- auto x = pq.top();
- int j = x.second;
- int id = x.first.second;
- pq.pop();
- if(++currPointers[j] < bestDists[rv[i][j]].size()){
- pq.push(make_pair(bestDists[rv[i][j]][currPointers[j]], j));
- }
- if(!occour[id]){
- occour[id] = true;
- bestDists[i].push_back(x.first);
- }
- }
- for(auto &x : bestDists[i]) x.first++;
- if(bestDists[i].size() < MAXK) bestDists[i].push_back({0, i});
- for(auto x : bestDists[i]) occour[x.second] = false;
- }
- vector<bool> on(n, true);
- while(q--){
- int x, y; scanf("%d %d", &x, &y); x--;
- vector<int> currOff;
- int before = 0;
- while(y--){
- int z; scanf("%d", &z); z--;
- on[z] = false;
- currOff.push_back(z);
- if(z <= x) before++;
- }
- int ans = -1;
- for(auto z : bestDists[x]){
- if(on[z.second]){
- ans = z.first; break;
- }
- }
- if(before <= x && ans == -1) ans = fullSolution(x, on);
- printf("%d\n", ans);
- for(auto z : currOff) on[z] = true;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement