现在尝试去掉重边加上强力优化，但是依然TLE.....
```cpp
#include <bits/stdc++.h>
using namespace std;
#define N 300005
const int inf = 2e9;
template <class T>
inline void read(T& a){
T x = 0, s = 1;
char c = getchar();
while(!isdigit(c)){ if(c == '-') s = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + (c ^ '0'); c = getchar(); }
a = x * s;
return ;
}
struct node{
int u, v, next;
} ;
struct tu{
public:
node t[N << 2];
int f[N];
public:
int bian;
inline void add(int u, int v){
this -> bian++;
t[bian] = (node){u, v, f[u]}, f[u] = this -> bian;
return ;
}
tu(int bian = 0){
this -> bian = bian;
return ;
}
} T, G;
int n , k;
char s[N];
int h[N], w[N];
inline int min(int a , int b){return a < b ? a : b ;}
inline int max(int a , int b){return a > b ? a : b ;}
int dfn[N], low[N];
int stac[N], top = 0;
bool vis[N];
int siz[N], scc[N], cnt = 0, id = 0;
void tarjan(int now){
dfn[now] = low[now] = ++id;
stac[++top] = now;
vis[now] = 1;
for(int i = T.f[now]; i; i = T.t[i].next){
int v = T.t[i].v;
if(!dfn[v]){
tarjan(v);
low[now] = min(low[now], low[v]);
}
else if(vis[v]) low[now] = min(low[now], dfn[v]);
}
if(dfn[now] == low[now]){
int cur;
cnt++;
do{
cur = stac[top--];
scc[cur] = cnt;
siz[cnt] += w[cur]; // 排除超级源点的影响
vis[cur] = 0;
} while(cur != now);
}
return ;
}
int ans = 0;
int d[N];
int q[N];
void spfa(int s){
int head = 0, tail = -1;
q[++tail] = s;
vis[s] = 1;
d[s] = siz[s];
while(head <= tail){
int now = q[head % N]; head++;
vis[now] = 0;
for(int i = G.f[now]; i; i = G.t[i].next){
int v = G.t[i].v;
if(d[v] < d[now] + siz[v]){
d[v] = d[now] + siz[v];
if(!vis[v]) q[++tail % N] = v, vis[v] = 1;
}
}
}
return ;
}
inline bool cmp(node A, node B) {
return (A.u == B.u) ? A.v < B.v : A.u < B.u;
}
int main(){
read(n), read(k);
for(int i = 1; i <= n; ++i)
read(h[i]), w[i] = 1;
w[n + 1] = 0;
h[0] = h[n + 1] = inf;
for(int i = 1; i <= n; ++i){
if(h[i - 1] <= h[i]) T.add(i, i - 1);
if(h[i + 1] <= h[i]) T.add(i, i + 1);
}
for(int i = 1; i <= n; ++i)
T.add(n + 1, i);
scanf("%s", s + 1);
for(int i = 1; i <= n; ++i)
if(s[i] == 'T') T.add(i, n + 1);
for(int i = 1; i <= n + 1; i++)
if(!dfn[i]) tarjan(i);
sort(T.t + 1, T.t + T.bian + 1, cmp); // 去掉重边
for(int i = 1; i <= T.bian; ++i){
int u = T.t[i].u, v = T.t[i].v;
if(u == T.t[i - 1].u && v == T.t[i - 1].v) continue;
if(scc[u] != scc[v] && scc[u] && scc[v]) // 可以到达的点才加入新图
G.add(scc[u], scc[v]);
}
memset(vis, 0, sizeof(vis));
spfa(scc[k]);
for(int i = 1; i <= cnt; ++i)
ans = max(ans, d[i]);
printf("%d\n", ans);
return 0;
}
```
by 青鸟_Blue_Bird @ 2020-10-29 17:32:13
https://www.luogu.com.cn/record/40760249
记录(最新)
by 青鸟_Blue_Bird @ 2020-10-29 17:36:12
蒟蒻去重边写假了，此贴终结
by 青鸟_Blue_Bird @ 2020-10-29 18:03:03
%%%% 巨佬
by SS_Chara @ 2020-10-29 20:07:53