差0.08秒，求优化

linyukun @ 2023-03-03 11:25:09

#include<bits/stdc++.h>
using namespace std;
int n,m,ru[1005],a[1005][1005],s,k,cnt=-1,st,e;
bool vis[1005];
queue<int>q;
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=0;i<m;i++){
        memset(vis,0,sizeof(vis));
        cin>>s;
        for(int j=0;j<s;j++){
            cin>>k;
            if(j==0)st=k;
            if(j==s-1)e=k;
            vis[k]=1;
        }
        for(int j=st;j<=e;j++){
            if(!vis[j]){
                for(int z=st;z<=e;z++){
                    if(vis[z]&&a[z][j]==0){
                        a[z][j]=1;
                        ru[j]++;
                    }
                }
            }
        }
    }
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++){
        a[0][i]=1;
        ru[i]++;
    }
    q.push(0);
    vis[0]=1;
    while(!q.empty()){
        cnt++;
        while(!q.empty()){
            int x=q.front();
            for(int i=1;i<=n;i++){
                if(a[x][i]&&vis[i]==0){
                    ru[i]--;
                }
            }
            q.pop();
        }
        for(int i=1;i<=n;i++){
            if(ru[i]==0&&vis[i]==0){
                vis[i]=1;
                q.push(i);
            }
        }
    }
    cout<<cnt<<endl;
    return 0;
}

by cn_ryh @ 2023-03-03 11:38:34

@linyukun 加了读入输出优化，不开 O_2 能卡过。

#include<bits/stdc++.h>
using namespace std;
int n,m,ru[1001],a[1001][1001],s,k,cnt=-1,st,e;
bool vis[1001];
queue<int>q;
void read(int &p)
{
    p = 0;
    int k = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
        {
            k = -1;
        }
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        p = p * 10 + c - '0';
        c = getchar();
    }
    p *= k;
    return;
}
void write_(int x)
{
    if(x < 0)
    {
        putchar('-');
        x = -x;
    }
    if(x>9)
    {
        write_(x/10);
    }
    putchar(x%10+'0');
}
void writesp(int x)
{
    write_(x);
    putchar(' ');
}
void writeln(int x)
{
    write_(x);
    putchar('\n');
}
int main(){
    read(n),read(m);
    for(int i=0;i<m;i++){
        memset(vis,0,sizeof(vis));
        read(s);
        for(int j=0;j<s;j++){
            read(k);
            if(j==0)st=k;
            if(j==s-1)e=k;
            vis[k]=1;
        }
        for(int j=st;j<=e;j++){
            if(!vis[j]){
                for(int z=st;z<=e;z++){
                    if(vis[z]&&a[z][j]==0){
                        a[z][j]=1;
                        ru[j]++;
                    }
                }
            }
        }
    }
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++){
        a[0][i]=1;
        ru[i]++;
    }
    q.push(0);
    vis[0]=1;
    while(!q.empty()){
        cnt++;
        while(!q.empty()){
            int x=q.front();
            for(int i=1;i<=n;i++){
                if(a[x][i]&&vis[i]==0){
                    ru[i]--;
                }
            }
            q.pop();
        }
        for(int i=1;i<=n;i++){
            if(ru[i]==0&&vis[i]==0){
                vis[i]=1;
                q.push(i);
            }
        }
    }
    writeln(cnt);
    return 0;
}

by cn_ryh @ 2023-03-03 11:39:52

@linyukun 提交记录 无O_2

by _Adolf_Hitler_ @ 2023-03-03 12:09:27

cin,cout

改成```cpp scanf,printf

试试

by linyukun @ 2023-03-03 12:37:19

@ryh2007316 谢谢老哥

by linyukun @ 2023-03-03 12:38:18

@JODAN_POOLE 不行的，先试的这个方法，反而会多0.02秒

by Allen_yang @ 2023-05-12 16:40:25

@cn_ryh 这题标签里本来就有O_2 ，你手动开不开都一样，都会自动开

by cn_ryh @ 2023-05-12 16:42:41

@Allen_yang QwQ....但是我手动 O2 过了，不开没过....

by Allen_yang @ 2023-05-12 16:43:57

@cn_ryh 6

by cn_ryh @ 2023-05-12 16:44:08

@Allen_yang 啊...不对，不开过了./..