Advertisement
YEZAELP

o62_oct_c1_highway

Jan 26th, 2022
944
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using pi = pair <int, int>;
  5. const int N = 1e5 + 10;
  6. const int Q = 2e5 + 10;
  7. vector <int> g[N], rg[N];
  8. bool open[N], fr1[N], frn[N];
  9. pi query[Q];
  10. int n, m, q;
  11. void Debug();
  12.  
  13. void dfs(int u){
  14.     fr1[u] = true;
  15.     for(auto v: g[u]){
  16.         if(open[v] and !fr1[v]) dfs(v);
  17.     }
  18. }
  19.  
  20. void rdfs(int u){
  21.     frn[u] = true;
  22.     for(auto v: rg[u]){
  23.         if(open[v] and !frn[v]) rdfs(v);
  24.     }
  25. }
  26.  
  27. int main(){
  28.  
  29.     scanf("%d %d %d", &n, &m, &q);
  30.  
  31.     for(int i = 1; i <= m; i ++){
  32.         int u, v;
  33.         scanf("%d %d", &u, &v);
  34.         g[u].push_back(v);
  35.         rg[v].push_back(u);
  36.     }
  37.  
  38.     for(int i = 1; i <= n; i ++)
  39.         open[i] = true;
  40.  
  41.     for(int i = 1, opr, x; i <= q; i ++){
  42.         scanf("%d %d", &opr, &x);
  43.         query[i] = {opr, x};
  44.         if(opr == 1) open[x] = false;
  45.     }
  46.  
  47.     dfs(1), rdfs(n);
  48.  
  49.     stack <int> ans;
  50.     for(int i = q, opr, x; i >= 1; i --){
  51.         opr = query[i].first,
  52.         x = query[i].second;
  53.         if(opr == 1){
  54.             open[x] = true;
  55.             for(auto v: rg[x]){
  56.                 if(fr1[v]){
  57.                     dfs(x);
  58.                     break;
  59.                 }
  60.             }
  61.             for(auto v: g[x]){
  62.                 if(frn[v]){
  63.                     rdfs(x);
  64.                     break;
  65.                 }
  66.             }
  67.         }
  68.         else if(opr == 2){
  69.             ans.push(fr1[x] and frn[x]);
  70.         }
  71.     }
  72.  
  73.     while(!ans.empty()){
  74.         printf("%d ", ans.top());
  75.         ans.pop();
  76.     }
  77.  
  78.     return 0;
  79. }
  80.  
  81. void Debug(){
  82.     printf("Debug\n");
  83.     printf(" open : ");
  84.     for(int i = 1; i <= n; i ++) printf("%d ", open[i]); printf("\n");
  85.     printf(" from1 : ");
  86.     for(int i = 1; i <= n; i ++) printf("%d ", fr1[i]); printf("\n");
  87.     printf(" fromn : ");
  88.     for(int i = 1; i <= n; i ++) printf("%d ", frn[i]); printf("\n");
  89.     printf("\n");
  90. }
Advertisement
RAW Paste Data Copied
Advertisement