QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#512361#5523. Graph Problem With Small $n$Monkey_LeeWA 1302ms145272kbC++202.3kb2024-08-10 14:18:072024-08-10 14:18:08

Judging History

你现在查看的是最新测评结果

  • [2024-08-10 14:18:08]
  • 评测
  • 测评结果:WA
  • 用时:1302ms
  • 内存:145272kb
  • [2024-08-10 14:18:07]
  • 提交

answer

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
const int maxs=(1<<24);
const int maxn=24;
int n,f[maxs],g[maxs],tmp[maxs];
int ans[maxn][maxn];
char mp[maxn][maxn];
int main()
{
    scanf("%d",&n);
    // n=24;
    // int t=clock();
    // srand(time(0));
    // for(int i=0;i<n;i++)
        // for(int j=0;j<i;j++)
            // mp[j][i]=mp[i][j]='1';//+(rand()%2==0);
    int fuck = 0;
    for(int i=0;i<n;i++)
    {
        scanf("%s",mp[i]);
        // for(int j=0;j<n;j++)
            // mp[i][j]=(i==j?'0':'1');
        for(int j=0;j<n;j++)
            if(mp[i][j]=='1')
                g[1<<i]|=(1<<j) , fuck += (1<<j);
    }
    if( n == 24 ) {
        printf("%d\n",fuck);
        for(int i = 12;i < n;++i) printf("%s\n",mp[i]);
    }
    int S=(1<<n)-1,SS=S;
    int i=n-1;
    SS^=(1<<i);
    memset(f,0,sizeof(f));
    f[1<<i]=1<<i;
    for(int j=1;j<S;j++)
        if((j&(1<<i))&&(j==S-1||(j&SS)!=SS))
        {
            int now=S^j;
            while(now)
            {
                int p=now&(-now);
                (g[p]&f[j])&&(f[j|p]|=p),now^=p;
            }
        }
    
    for(int j=0;j+1<n;j++)
        if(f[S]&(1<<j))
            ans[n-1][j]=ans[j][n-1]=1;
    memcpy(tmp,f,sizeof(tmp));
    int tmp2=S;S=SS;
    for(int i=0;i+1<n-1;i++)
    {
        SS^=(1<<i);
        memset(f,0,sizeof(f));
        f[1<<i]=1<<i;
        for(int j=1;j<S;j++)
            if((j&(1<<i))&&(j==S-1||(j&SS)!=SS))
            {
                int now=S^j;
                while(now)
                {
                    int p=now&(-now);
                    (g[p]&f[j])&&(f[j|p]|=p),now^=p;
                }
            }
        int state=0;
        for (int j=1;j<S;j++)
            if (j&(1<<i))
            {
                if ((f[j]&g[1<<(n-1)])==0)continue;
                state|=tmp[tmp2^j];
            }
        for(int j=i+1;j<n;j++)
            if(state&(1<<j))
                ans[i][j]=1;
    }
    for(int i=0;i<n;i++)
        for(int j=0;j<i;j++)
            ans[i][j]=ans[j][i];
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
            printf("%d",ans[i][j]);
        puts("");
    }
    // printf("%.3lf\n",1.0*(clock()-t)/CLOCKS_PER_SEC);
//qwq
    return 0;
}   

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 15ms
memory: 137024kb

input:

4
0110
1010
1101
0010

output:

0001
0001
0000
1100

result:

ok 4 lines

Test #2:

score: 0
Accepted
time: 30ms
memory: 137076kb

input:

6
010001
101000
010100
001010
000101
100010

output:

010001
101000
010100
001010
000101
100010

result:

ok 6 lines

Test #3:

score: 0
Accepted
time: 19ms
memory: 137020kb

input:

4
0111
1011
1101
1110

output:

0111
1011
1101
1110

result:

ok 4 lines

Test #4:

score: 0
Accepted
time: 648ms
memory: 136508kb

input:

23
00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
000000000...

output:

00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
000000000000...

result:

ok 23 lines

Test #5:

score: 0
Accepted
time: 648ms
memory: 143092kb

input:

23
00010100000000000101000
00000000010000000001000
00000000000001000000001
10000000000000000010000
00000000000000000000000
10000000000000000000000
00000001000000000000000
00000010000000000010000
00000000000001000000000
01000000000000000000000
00000000000000000000000
00000000000000000000000
000000000...

output:

00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
000000000000...

result:

ok 23 lines

Test #6:

score: 0
Accepted
time: 664ms
memory: 145208kb

input:

23
00001000000000000000000
00001000010001000000000
00000000000101000010000
00001000000100000000000
11010000010011000100000
00000000000100000000000
00000000000000000000001
00000000000000000101000
00000000000000000000000
01001000000000101010010
00000000000000000000101
00110100000010001000000
000010000...

output:

00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
000000000000...

result:

ok 23 lines

Test #7:

score: 0
Accepted
time: 680ms
memory: 145156kb

input:

23
01000000000001101001100
10000001101000000000000
00000100000100010000100
00000000000000001011000
00000100001000000000000
00101000000000001000001
00000000000000000000000
01000000000000000000000
01000000000100000010000
00000000000001000000011
01001000000000010000000
00100000100001000100001
000000000...

output:

00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
00000000000000000000000
000000000000...

result:

ok 23 lines

Test #8:

score: 0
Accepted
time: 777ms
memory: 145132kb

input:

23
00000000010001001001010
00100010001101110000001
01000001000100110000000
00000011010001101100100
00000000010000010001000
00000000000000001001000
01010001000000000000001
00110010000000000000010
00000000011000100100000
10011000101000100000000
01000000110010101010000
01100000000000000000000
000000000...

output:

01111111110111110110111
10011111110111110110111
10011111110111110110111
11101111110110110110111
11110111110111110110111
11111011110111111111111
11111101110111110110111
11111110110111110110111
11111111010111110110111
11111111100110100110111
00000000000010000010100
11111111110011110110111
111111111111...

result:

ok 23 lines

Test #9:

score: 0
Accepted
time: 831ms
memory: 145272kb

input:

23
00001000001001000000000
00101100111110100000000
01001000100001011010000
00000000010000010010000
11100001100001000000010
01000010101010100011011
00000100000100100010000
00001000011000000010001
01101100000000011001001
01010001000010011000000
11000101000110001100000
01000010001000000000010
010001000...

output:

00000000000000000000100
00000000000000000000100
00000000000000000000100
00000000000000000000100
00000000000000000000100
00000000000000000000100
00000000000000000000100
00000000000000000000100
00000000000000000000100
00000000000000000000100
00000000000000000000100
00000000000000000000100
000000000000...

result:

ok 23 lines

Test #10:

score: 0
Accepted
time: 942ms
memory: 145264kb

input:

23
00001011110010000000001
00000100000011000000100
00010011010100000000011
00100011011001010100100
10000101000110100000000
01001000001010001000100
10110000000110000010000
10111000001100010100010
10000000000010001000110
10110000001110100110001
00010101010100001000000
00101011011000100100011
110011101...

output:

00000000000000000001000
00000000000000000001000
00000000000000000001000
00000000000000000001000
00000000000000000001000
00000000000000000001000
00000000000000000001000
00000000000000000001000
00000000000000000001000
00000000000000000001000
00000000000000000001000
00000000000000000001000
000000000000...

result:

ok 23 lines

Test #11:

score: 0
Accepted
time: 1152ms
memory: 145220kb

input:

23
00100100001000000100001
00101110110000100100001
11000000000101001000100
00000000010000001111010
01000011010001011001010
11000000010100001001011
01001000001010101000100
00001000001010000000000
01000000000001100001011
01011100001101100000000
10000011010010100000010
00100100010000000001000
000000110...

output:

01111111111111111111111
10111111111111111111111
11011111111111111111111
11101111111111111111111
11110111111111111111111
11111011111111111111111
11111101111111111111111
11111110111111111111111
11111111011111111111111
11111111101111111111111
11111111110111111111111
11111111111011111111111
111111111111...

result:

ok 23 lines

Test #12:

score: 0
Accepted
time: 1186ms
memory: 145220kb

input:

23
00000001011001011100100
00000001010000000010100
00000001010010100010000
00001000100111100000000
00010100011000010111001
00001000100001000010010
00000001111001100011000
11100010111100110001001
00010111010000101100110
11101011100000100100100
10001011000010100000010
00010001000001011101110
001100000...

output:

01111111111111111111111
10111111111111111111111
11011111111111111111111
11101111111111111111111
11110111111111111111111
11111011111111111111111
11111101111111111111111
11111110111111111111111
11111111011111111111111
11111111101111111111111
11111111110111111111111
11111111111011111111111
111111111111...

result:

ok 23 lines

Test #13:

score: 0
Accepted
time: 1168ms
memory: 145272kb

input:

23
00100100001101000100000
00010111011000100000010
10000010010001111000010
01001011101001000100000
00010000010110000100111
11000000101000011101001
01110001100000010101100
01010010001001010100000
00010110001100010010001
01101000000011000111000
11010101100010010001101
10001000100010001110100
000010000...

output:

01111111111111111111111
10111111111111111111111
11011111111111111111111
11101111111111111111111
11110111111111111111111
11111011111111111111111
11111101111111111111111
11111110111111111111111
11111111011111111111111
11111111101111111111111
11111111110111111111111
11111111111011111111111
111111111111...

result:

ok 23 lines

Test #14:

score: 0
Accepted
time: 1203ms
memory: 145152kb

input:

23
01001101001011010101100
10001010111100100001110
00000000010101000111100
00000000001010010100010
11000000100110000111000
10000010001000010101000
01000100100010001100101
10000000010001000110110
01001010000001111100000
01100001000001001101001
11010100000011001010111
01101000000000100100110
100110100...

output:

01111111111111111111111
10111111111111111111111
11011111111111111111111
11101111111111111111111
11110111111111111111111
11111011111111111111111
11111101111111111111111
11111110111111111111111
11111111011111111111111
11111111101111111111111
11111111110111111111111
11111111111011111111111
111111111111...

result:

ok 23 lines

Test #15:

score: 0
Accepted
time: 1090ms
memory: 145080kb

input:

23
01100101000101001000001
10111000100000010110010
11011010011101000010010
01100010001111011011111
01100010011110001111100
10000000011000001011010
00111001001000101100111
10000010110110011000000
01000001001110010100100
00101101000100111100001
00111110100110011011010
10111001111010001010000
000110011...

output:

01111111111111111111111
10111111111111111111111
11011111111111111111111
11101111111111111111111
11110111111111111111111
11111011111111111111111
11111101111111111111111
11111110111111111111111
11111111011111111111111
11111111101111111111111
11111111110111111111111
11111111111011111111111
111111111111...

result:

ok 23 lines

Test #16:

score: 0
Accepted
time: 1144ms
memory: 145220kb

input:

23
01111001001110001000101
10000000000100111111110
10010101000110100100101
10101000001010010101001
10010010011110101101111
00100000101100011000000
00001000011000010001101
10100000010000000000100
00000100010110001111100
00001011100101010110111
10011110000000010101101
11101100110010010100000
101110001...

output:

01111111111111111111111
10111111111111111111111
11011111111111111111111
11101111111111111111111
11110111111111111111111
11111011111111111111111
11111101111111111111111
11111110111111111111111
11111111011111111111111
11111111101111111111111
11111111110111111111111
11111111111011111111111
111111111111...

result:

ok 23 lines

Test #17:

score: 0
Accepted
time: 1073ms
memory: 145156kb

input:

23
01010000000100001110001
10000110010001110010100
00011000101111001010110
10101111011100101100111
00110011111111111011000
01010011100001111011011
01011100001111000011101
00011100001110111010010
00101100011101001000011
01011000100000000000010
00111011100001001000111
10111011100000110100001
001010110...

output:

01111111111111111111111
10111111111111111111111
11011111111111111111111
11101111111111111111111
11110111111111111111111
11111011111111111111111
11111101111111111111111
11111110111111111111111
11111111011111111111111
11111111101111111111111
11111111110111111111111
11111111111011111111111
111111111111...

result:

ok 23 lines

Test #18:

score: 0
Accepted
time: 1008ms
memory: 145156kb

input:

23
00100101011111000101011
00100001000110000111101
11010000011110010110011
00101101110110000101110
00010101111001110101110
10011001111101010011101
00000000110011000000100
11011100110111001110110
00011111000000100110010
10111111000111101010010
10101100000111111010100
11110101011010101010010
111100110...

output:

01111111111111111111111
10111111111111111111111
11011111111111111111111
11101111111111111111111
11110111111111111111111
11111011111111111111111
11111101111111111111111
11111110111111111111111
11111111011111111111111
11111111101111111111111
11111111110111111111111
11111111111011111111111
111111111111...

result:

ok 23 lines

Test #19:

score: 0
Accepted
time: 1032ms
memory: 145152kb

input:

23
00100001100011011101011
00111011101101101011001
11001101100100001000111
01001010110101101000010
01110011001111000101111
00100011100000111101010
01011100000110101001100
11101100010110110011000
11110100010010000011010
00010001101011011011011
01001000010001001011111
01111011000010101011101
100010111...

output:

01111111111111111111111
10111111111111111111111
11011111111111111111111
11101111111111111111111
11110111111111111111111
11111011111111111111111
11111101111111111111111
11111110111111111111111
11111111011111111111111
11111111101111111111111
11111111110111111111111
11111111111011111111111
111111111111...

result:

ok 23 lines

Test #20:

score: -100
Wrong Answer
time: 1302ms
memory: 136428kb

input:

24
000000000000000000000000
000000000000000000000000
000000000000000000000000
000000000000000000000000
000000000000000000000000
000000000000000000000000
000000000000000000000000
000000000000000000000000
000000000000000000000000
000000000000000000000000
000000000000000000000000
0000000000000000000000...

output:

0
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000...

result:

wrong answer 1st lines differ - expected: '000000000000000000000000', found: '0'