Advertisement
paulomiranda98

Untitled

Jun 2nd, 2021
1,440
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.22 KB | None | 0 0
  1. //Testando o código do  pauloamed
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5. #define MAXN 100010
  6. #define MAXK 100
  7. #define ppiii pair<pair<int,int>,int>
  8.  
  9. int n;
  10. vector<int> v[MAXN];
  11. vector<int> rv[MAXN];
  12.  
  13. int pd[MAXN];
  14.  
  15. int fullSolution(int x, vector<bool> &on){
  16.   memset(pd, -1, sizeof(pd));
  17.  
  18.   int ans = -1;
  19.   pd[x] = 0;
  20.   for(int i = x; i >= 0; --i){
  21.     if(pd[i] != -1){
  22.       for(auto y : rv[i]){
  23.           pd[y] = max(pd[y], pd[i] + 1);
  24.       }
  25.     }
  26.     if(on[i]) ans = max(ans, pd[i]);
  27.   }
  28.   return ans;
  29. }
  30.  
  31.  
  32. int main(){
  33.   int m, q; scanf("%d %d %d", &n, &m, &q);
  34.   for(int i = 0; i < m; ++i){
  35.     int a, b;  scanf("%d %d", &a, &b);; a--, b--;
  36.     if(a > b) swap(a, b);
  37.     v[a].push_back(b);
  38.     rv[b].push_back(a);
  39.   }
  40.  
  41.   // cout << block << endl;
  42.  
  43.   vector<vector<pair<int,int>>> bestDists(n);
  44.  
  45.   vector<bool> occour(n);
  46.   for(int i = 0; i < n; ++i){
  47.     vector<int> currPointers(rv[i].size());
  48.  
  49.     priority_queue<ppiii, vector<ppiii>, less<ppiii>> pq;
  50.     for(int j = 0; j < rv[i].size(); ++j){
  51.       pq.push(make_pair(bestDists[rv[i][j]].front(), j));
  52.     }
  53.  
  54.     while(pq.size() && bestDists[i].size() < MAXK){
  55.       auto x = pq.top();
  56.       int j = x.second;
  57.       int id = x.first.second;
  58.       pq.pop();
  59.  
  60.       if(++currPointers[j] < bestDists[rv[i][j]].size()){
  61.         pq.push(make_pair(bestDists[rv[i][j]][currPointers[j]], j));
  62.       }
  63.  
  64.       if(!occour[id]){
  65.         occour[id] = true;
  66.         bestDists[i].push_back(x.first);
  67.       }
  68.     }
  69.  
  70.     for(auto &x : bestDists[i]) x.first++;
  71.     if(bestDists[i].size() < MAXK) bestDists[i].push_back({0, i});
  72.     for(auto x : bestDists[i]) occour[x.second] = false;
  73.   }
  74.  
  75.   vector<bool> on(n, true);
  76.   while(q--){
  77.     int x, y; scanf("%d %d", &x, &y); x--;
  78.     vector<int> currOff;
  79.  
  80.     int before = 0;
  81.     while(y--){
  82.       int z; scanf("%d", &z); z--;
  83.       on[z] = false;
  84.       currOff.push_back(z);
  85.       if(z <= x) before++;
  86.     }
  87.  
  88.     int ans = -1;
  89.     for(auto z : bestDists[x]){
  90.       if(on[z.second]){
  91.         ans = z.first; break;
  92.       }
  93.     }
  94.  
  95.     if(before <= x && ans == -1) ans = fullSolution(x, on);
  96.     printf("%d\n", ans);
  97.     for(auto z : currOff) on[z] = true;
  98.   }
  99. }
  100.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement