60分RE求助!!!

P1983 [NOIP2013 普及组] 车站分级

Dark_Van @ 2019-02-05 15:17:18

一开始RE只有30分

后来数组开大了点,还是RE,60分,求助dalao!

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
const int MAX = 10100;

int n,m,rud[MAX]={0};
int first[MAX];
int ans=0;

int read(){
    int x=0,w=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')w=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    return x*w;
}

struct edge{
    int u,v,next;
}e[MAX];

struct node{
    int u,len;
};

int cnt=0;
void insert(int u,int v){
    ++cnt;e[cnt].u=u;e[cnt].v=v;e[cnt].next=first[u];first[u]=cnt;
}

node makenode(int u,int len){
    node qwq;
    qwq.len=len;qwq.u=u;
    return qwq;
}

queue<node> q;
void topo(){
    for(int i=1;i<=n;i++){
        if(rud[i]==0)q.push(makenode(i,1));
    }
    ans=1;
    while(!q.empty()){
        int u=q.front().u,len=q.front().len;
        q.pop();
        for(int i=first[u];i!=-1;i=e[i].next){
            int v=e[i].v;
            rud[v]--;
            if(rud[v]==0){
                q.push(makenode(v,len+1));
                ans=max(ans,len+1);
            } 
        }
    }
} 

int con[MAX][MAX]={0};
int main(){
    memset(first,-1,sizeof(first));
    n=read();m=read();
    int temp[MAX],stop[MAX];
    for(int i=1;i<=m;i++){
        memset(stop,0,sizeof(stop));
        int tot=read();
        for(int j=1;j<=tot;j++){
            temp[j]=read();
            stop[temp[j]]=1;
        }
        for(int j=temp[1];j<=temp[tot];j++){
            if(!stop[j]){
                for(int k=1;k<=tot;k++){
                    if(!con[j][temp[k]]){
                        con[j][temp[k]]=1;
                        insert(j,temp[k]);
                        rud[temp[k]]++;
                    }
                }
            }
        }
    }
    topo();
    printf("%d",ans);
    return 0;
}

by 花园Serena @ 2019-02-05 16:12:04

冲您这名字就要%%%


by Dark_Van @ 2019-02-05 18:50:52

@Van♂様年华 都是同♂志


by arr2 @ 2019-02-17 08:47:10

邻接表开大 你邻接表大小就10010 我之前开到100010都re 开到1000010就好了


by 万弘 @ 2019-04-21 13:03:42

@Dark_Van 我原本也是这样,开了5e6都过不去,后来发现图中有很多的重边(最坏约n^2m条,甚至超1e8),所以要再开一个二维数组判重边

before:

#define maxn 2011
#define maxm 5000011
ll n,m;
struct Edge
{
    ll v,nxt;
}e[maxm];
ll cnt=0,last[maxn],ind[maxn];
void adde(ll u,ll v)
{
    ++ind[v];
    e[++cnt].v=v;
    e[cnt].nxt=last[u];last[u]=cnt;
}

after:

#define maxn 2011
#define maxm 2000011
ll n,m;
struct Edge
{
    ll v,nxt;
}e[maxm];
ll cnt=0,last[maxn],ind[maxn];
bool p[maxn][maxn];
inline void adde(ll u,ll v)
{
    if(p[u][v])return;
    p[u][v]=1;
    ++ind[v];
    e[++cnt].v=v;
    e[cnt].nxt=last[u];last[u]=cnt;
}

PS:要稍微卡一下常,否则T一个点


|