代码求hack
  • 板块P11073 Game King
  • 楼主CAICAIA
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/9/18 10:10
  • 上次更新2024/9/18 17:38:11
查看原帖
代码求hack
704655
CAICAIA楼主2024/9/18 10:10

不知道那里假了,求hack。

大样例过不了,能不能给个小一点的hack

#include<bits/stdc++.h>
using namespace std;
const long long MX=10000100,INF=0x3f3f3f3f;
vector<long long>vec[MX];
long long low[MX]={0},dfn[MX]={0},siz[MX]={0},tim=0;
long long belong[MX]={0},cnt=0;
long long flag[MX]={0};stack<long long>st;
void tarjan(int now){
    dfn[now]=++tim,low[now]=tim;st.push(now);flag[now]=1;
    for(auto to:vec[now]){
        if(!dfn[to]){
            tarjan(to);
            low[now]=min(low[now],low[to]);
        }
        else if(flag[to]){
            low[now]=min(low[now],low[to]);
        }
    }
    if(dfn[now]==low[now]){
        int x;cnt++;
        do{
            x=st.top();st.pop();flag[x]=0;siz[cnt]++;
            belong[x]=cnt;
        }while(x!=now);
    }
}
long long n,m;
vector<long long>vec2[MX];
long long in[MX]={0};
signed main(){
    scanf("%lld%lld",&n,&m);
    for(long long i=1;i<=m;i++){
        long long x,y;scanf("%lld%lld",&x,&y);
        vec[x].push_back(y);
    }
    for(long long i=1;i<=n;i++)if(!dfn[i])  tarjan(i);
    long long sum=0,x=0,ls;
    for(long long i=1;i<=n;i++){
        for(auto j:vec[i]){
            if(belong[i]==belong[j])  continue;
            vec2[belong[i]].push_back(belong[j]);
            // printf("check %lld %lld\n",belong[i],belong[j]);
            in[belong[j]]++;
        }
    }
    queue<long long>qu;long long ans=0;
    for(long long i=1;i<=cnt;i++)  if(!in[i])sum++,qu.push(i);
    if(sum==1)  ans+=siz[qu.front()];
    while(!qu.empty()){
        long long now=qu.front();qu.pop();
        printf("now=%d %d\n",now,sum);
        // if(sum==1&&x==0)  ans+=siz[now];
        sum--;
        for(auto to:vec2[now]){
            if(!--in[to]){
                qu.push(to);
                x++;ls=to;
            }
        }
        if(!sum){  
            if(x==1)  ans+=siz[ls],printf("ls=%d\n",ls);
            sum=x,x=0,ls=0;
        }
    } 
    cout<<ans;
    return 0;
}
/*
        CCCCCCCCCCCCC               AAA               IIIIIIIIII      CCCCCCCCCCCCC               AAA               IIIIIIIIII               AAA               
     CCC::::::::::::C              A:::A              I::::::::I   CCC::::::::::::C              A:::A              I::::::::I              A:::A              
   CC:::::::::::::::C             A:::::A             I::::::::I CC:::::::::::::::C             A:::::A             I::::::::I             A:::::A             
  C:::::CCCCCCCC::::C            A:::::::A            II::::::IIC:::::CCCCCCCC::::C            A:::::::A            II::::::II            A:::::::A            
 C:::::C       CCCCCC           A:::::::::A             I::::I C:::::C       CCCCCC           A:::::::::A             I::::I             A:::::::::A           
C:::::C                        A:::::A:::::A            I::::IC:::::C                        A:::::A:::::A            I::::I            A:::::A:::::A          
C:::::C                       A:::::A A:::::A           I::::IC:::::C                       A:::::A A:::::A           I::::I           A:::::A A:::::A         
C:::::C                      A:::::A   A:::::A          I::::IC:::::C                      A:::::A   A:::::A          I::::I          A:::::A   A:::::A        
C:::::C                     A:::::A     A:::::A         I::::IC:::::C                     A:::::A     A:::::A         I::::I         A:::::A     A:::::A       
C:::::C                    A:::::AAAAAAAAA:::::A        I::::IC:::::C                    A:::::AAAAAAAAA:::::A        I::::I        A:::::AAAAAAAAA:::::A      
C:::::C                   A:::::::::::::::::::::A       I::::IC:::::C                   A:::::::::::::::::::::A       I::::I       A:::::::::::::::::::::A     
 C:::::C       CCCCCC    A:::::AAAAAAAAAAAAA:::::A      I::::I C:::::C       CCCCCC    A:::::AAAAAAAAAAAAA:::::A      I::::I      A:::::AAAAAAAAAAAAA:::::A    
  C:::::CCCCCCCC::::C   A:::::A             A:::::A   II::::::IIC:::::CCCCCCCC::::C   A:::::A             A:::::A   II::::::II   A:::::A             A:::::A   
   CC:::::::::::::::C  A:::::A               A:::::A  I::::::::I CC:::::::::::::::C  A:::::A               A:::::A  I::::::::I  A:::::A               A:::::A  
     CCC::::::::::::C A:::::A                 A:::::A I::::::::I   CCC::::::::::::C A:::::A                 A:::::A I::::::::I A:::::A                 A:::::A 
        CCCCCCCCCCCCCAAAAAAA                   AAAAAAAIIIIIIIIII      CCCCCCCCCCCCCAAAAAAA                   AAAAAAAIIIIIIIIIIAAAAAAA                   AAAAAAA
*/
2024/9/18 10:10
加载中...