Guest User

Untitled

a guest
Jul 14th, 2020
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.91 KB | None | 0 0
  1. #pragma GCC optimize("Ofast")
  2. #pragma loop_opt(on)
  3. #include<cstdio>
  4. #define FOR(i,n) for(int i=0;i<n;++i)
  5. inline char readchar(){
  6.     const int S = 1<<20;
  7.     static char buf[S], *p = buf, *q = buf;
  8.     if(p==q&&(q=(p=buf)+fread(buf,1,S,stdin))==buf) return EOF;
  9.     return *p++;
  10. }
  11. inline int R(){
  12.     int ans = 0, c = readchar();
  13.     while((c<'0'||c>'9')&&c!=EOF) c=readchar();
  14.     while(c>='0'&&c<='9') ans=(ans<<3)+(ans<<1)+(c^'0'), c=readchar();
  15.     return ans;
  16. }
  17. inline int min(int a, int b){
  18.     return a < b ? a : b;
  19. }
  20. #include<vector>
  21. using namespace std;
  22. const int N = 300001;
  23. int n, k, h[N];
  24. vector<int> adj[N];
  25.  
  26. int pre[N], id, low[N], scc[N];
  27. int S[N], p;
  28. bool inStack[N];
  29. void tarjan(int u){
  30.     low[u] = pre[u] = ++id;
  31.     S[p++] = u, inStack[u] = true;
  32.     for(int v: adj[u]){
  33.         if(pre[v] == 0){
  34.             tarjan(v);
  35.             low[u] = min(low[u], low[v]);
  36.         }
  37.         else if(inStack[v])
  38.             low[u] = min(low[u], pre[v]);
  39.     }
  40.     if(low[u] == pre[u]){
  41.         int v;
  42.         do{
  43.             v = S[--p];
  44.             inStack[v] = false;
  45.             scc[v] = u;
  46.         } while(v != u);
  47.     }
  48. }
  49.  
  50. int sccsz[N], subsize[N];
  51. vector<int> sccadj[N];
  52. int dfs(int u){
  53.     if(subsize[u] != 0) return subsize[u];
  54.     subsize[u] = sccsz[u];
  55.     int ans = 0;
  56.     for(int v: sccadj[u]){
  57.         ans = max(ans, dfs(v));
  58.     }
  59.     return subsize[u] += ans;
  60. }
  61.  
  62. int main(){
  63.     n = R(); k = R();
  64.     for(int i = 1; i <= n; ++i) h[i] = R();
  65.     adj[0].push_back(1);
  66.     for(int i = 2; i <= n; ++i){
  67.         if(h[i-1] <= h[i]) adj[i].push_back(i-1);
  68.         if(h[i] <= h[i-1]) adj[i-1].push_back(i);
  69.         adj[0].push_back(i);
  70.     }
  71.  
  72.     char c;
  73.     while(c != '.' and c != 'T') c = readchar();
  74.     for(int i = 1; i <= n; ++i){
  75.         if(c == 'T') adj[i].push_back(0);
  76.         c = readchar();
  77.     }
  78.  
  79.     for(int i = 1; i <= n; ++i)
  80.         if(pre[i] == 0) tarjan(i);
  81.  
  82.     for(int i = 1; i <= n; ++i) ++sccsz[scc[i]];
  83.  
  84.     for(int i = 0; i <= n; ++i)
  85.         for(int j: adj[i])
  86.             if(scc[i] != scc[j])
  87.                 sccadj[scc[i]].push_back(scc[j]);
  88.  
  89.     printf("%d", dfs(scc[k]));
  90.     return 0;
  91. }
Add Comment
Please, Sign In to add comment