记录详情

Time Exceeded

/in/foo.cc: In function 'void R_Int(int&)':
/in/foo.cc:9:5: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
     while(ch=getchar(),ch<'0'||ch>'9');a=(ch^48);
     ^~~~~
/in/foo.cc:9:40: note: ...this statement, but the latter is misleadingly indented as if it is guarded by the 'while'
     while(ch=getchar(),ch<'0'||ch>'9');a=(ch^48);
                                        ^
# 状态 耗时 内存占用
#1 Wrong Answer 42ms 22.551 MiB
#2 Wrong Answer 88ms 26.68 MiB
#3 Accepted 169ms 24.719 MiB
#4 Accepted 171ms 25.082 MiB
#5 Accepted 173ms 24.832 MiB
#6 Time Exceeded ≥1005ms ≥25.555 MiB

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
int n,m,S,p;
int a[maxn],val[maxn];
bool ed[maxn];
void R_Int(int &a){
    int ch;
    while(ch=getchar(),ch<'0'||ch>'9');a=(ch^48);
    while(ch=getchar(),ch>='0'&&ch<='9')a=a*10+(ch^48);
}

int h[maxn];
int dfn[maxn],low[maxn],ti;
int bel[maxn],tot;
struct Edge{
    int to,nxt;
}e[maxn];int tot_Edge;
void AddEdge(int from,int to){
    e[++tot_Edge]=(Edge){to,h[from]};
    h[from]=tot_Edge;
}
int st[maxn],Top;
bool ins[maxn];
void dfs(int u){
    dfn[u]=low[u]=++ti;
    ins[u]=1,st[++Top]=u;
    for(int i=h[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(!dfn[v]){
            dfs(v);
            low[u]=min(low[u],low[v]);
        }
        else if(ins[v])low[u]=min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u]){
        tot++;
        int t;
        do{
            ins[t=st[Top--]]=0;
            val[bel[t]=tot]+=a[t];
        }while(t!=u);
    }
}

int H[maxn];
bool END[maxn];
struct EDGE{
    int to,nxt;
}E[maxn];int TOT_EDGE;
void ADDEDGE(int from,int to){
    E[++TOT_EDGE]=(EDGE){to,H[from]};
    H[from]=TOT_EDGE;
}
void Rebuild(){
    for(int u=1;u<=n;u++)if(bel[u]){
        if(ed[u])END[bel[u]]=1;
        for(int i=h[u];i;i=e[i].nxt){
            int v=e[i].to;
            if(bel[u]!=bel[v])ADDEDGE(bel[u],bel[v]);
        }
    }
}
int f[maxn];
bool vis[maxn];
void Dp(int u){
    int mx=0;
    for(int i=H[u];i;i=E[i].nxt){
        int v=E[i].to;
        if(!vis[v])Dp(v);
        mx=max(mx,f[v]);
    }
    f[u]=max(mx+val[u],END[u]*val[u]);
}
int main(){
    R_Int(n),R_Int(m);
    for(int i=1,u,v;i<=m;i++){
        R_Int(u),R_Int(v);
        AddEdge(u,v);
    }
    for(int i=1;i<=n;i++)R_Int(a[i]);
    R_Int(S),R_Int(p);
    for(int i=1,x;i<=p;i++)R_Int(x),ed[x]=1;
    dfs(S);
    Rebuild();
    Dp(bel[S]);
    printf("%d\n",f[bel[S]]);
    return 0;
}

信息

递交者
类型
递交
题目
P1006 hitwh 2019 新生赛 G LFhase 与他的学术文章
语言
C++
递交时间
2020-12-17 20:18:07
评测时间
2020-12-17 20:18:21
评测机
分数
60
总耗时
≥1650ms
峰值内存
≥26.68 MiB