Submission #65511052

Source Code Expand

#include <bits/stdc++.h>
#define mod 998244353ll
using namespace std;
typedef long long ll;

int a[405][405],p[405],c[405];
ll fac[405];

int find(int x){
    return p[x]==p[p[x]]?p[x]:p[x]=find(p[x]);
}

int main(){
    int t,n;
    ios::sync_with_stdio(false);cin.tie(nullptr);
    cin>>t;fac[0]=1;
    for(int i=1;i<=400;i++)
        fac[i]=i*fac[i-1]%mod;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                cin>>a[i][j];
        bool ok=false;
        for(int i=1;i<=n;i++)
            if(!a[1][i] || !a[i][1])
                {ok=true;goto done;}
        for(int i=2;i<n;i++){
            for(int j=i+1;j<=n;j++)if(a[i][j]){
                int t=0;
                for(int k=2;k<=n;k++)if(a[i][k]!=a[j][k]){
                    if(t && t!=a[i][k]-a[j][k]){ok=true;goto done;}
                    t=a[i][k]-a[j][k];
                }
            }
        }
        done:if(ok){cout<<"0\n";continue;}
        for(int i=1;i<=n;i++)
            p[i]=i,c[i]=0;
        for(int i=2;i<n;i++){
            for(int j=i+1;j<=n;j++)if(find(i)!=find(j)){
                bool ok=true;
                for(int k=2;k<=n;k++)
                    if(a[i][k]!=a[j][k])
                        {ok=false;break;}
                if(ok)p[find(i)]=find(j);
            }
        }
        ll ans=1;
        for(int i=1;i<=n;i++)
            c[find(i)]++;
        for(int i=1;i<=n;i++)if(find(i)==i)
            ans=ans*fac[c[i]]%mod;
        cout<<ans<<'\n';
    }
    return 0;
}

Submission Info

Submission Time
Task D - Ancestor Relation
User PengAo
Language C++ 17 (gcc 12.2)
Score 700
Code Size 1583 Byte
Status AC
Exec Time 33 ms
Memory 4244 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 700 / 700
Status
AC × 1
AC × 94
Set Name Test Cases
Sample 01_sample_01.txt
All 01_sample_01.txt, 02_small_01.txt, 02_small_02.txt, 02_small_03.txt, 03_mid_1_01.txt, 03_mid_1_02.txt, 03_mid_1_03.txt, 03_mid_1_04.txt, 03_mid_1_05.txt, 03_mid_1_06.txt, 03_mid_1_07.txt, 03_mid_1_08.txt, 03_mid_1_09.txt, 03_mid_1_10.txt, 03_mid_1_11.txt, 03_mid_1_12.txt, 03_mid_1_13.txt, 03_mid_1_14.txt, 03_mid_1_15.txt, 04_mid_2_01.txt, 04_mid_2_02.txt, 04_mid_2_03.txt, 04_mid_2_04.txt, 04_mid_2_05.txt, 04_mid_2_06.txt, 04_mid_2_07.txt, 04_mid_2_08.txt, 04_mid_2_09.txt, 04_mid_2_10.txt, 04_mid_2_11.txt, 04_mid_2_12.txt, 04_mid_2_13.txt, 04_mid_2_14.txt, 04_mid_2_15.txt, 05_mid_3_01.txt, 05_mid_3_02.txt, 05_mid_3_03.txt, 05_mid_3_04.txt, 05_mid_3_05.txt, 06_mid_4_01.txt, 06_mid_4_02.txt, 06_mid_4_03.txt, 06_mid_4_04.txt, 06_mid_4_05.txt, 07_mid_5_01.txt, 07_mid_5_02.txt, 07_mid_5_03.txt, 07_mid_5_04.txt, 07_mid_5_05.txt, 08_max_1_01.txt, 08_max_1_02.txt, 08_max_1_03.txt, 08_max_1_04.txt, 08_max_1_05.txt, 08_max_1_06.txt, 08_max_1_07.txt, 08_max_1_08.txt, 08_max_1_09.txt, 08_max_1_10.txt, 08_max_1_11.txt, 08_max_1_12.txt, 08_max_1_13.txt, 08_max_1_14.txt, 08_max_1_15.txt, 09_max_2_01.txt, 09_max_2_02.txt, 09_max_2_03.txt, 09_max_2_04.txt, 09_max_2_05.txt, 09_max_2_06.txt, 09_max_2_07.txt, 09_max_2_08.txt, 09_max_2_09.txt, 09_max_2_10.txt, 09_max_2_11.txt, 09_max_2_12.txt, 09_max_2_13.txt, 09_max_2_14.txt, 09_max_2_15.txt, 10_max_3_01.txt, 10_max_3_02.txt, 10_max_3_03.txt, 10_max_3_04.txt, 10_max_3_05.txt, 11_max_4_01.txt, 11_max_4_02.txt, 11_max_4_03.txt, 11_max_4_04.txt, 11_max_4_05.txt, 12_max_5_01.txt, 12_max_5_02.txt, 12_max_5_03.txt, 12_max_5_04.txt, 12_max_5_05.txt
Case Name Status Exec Time Memory
01_sample_01.txt AC 1 ms 3464 KiB
02_small_01.txt AC 5 ms 3436 KiB
02_small_02.txt AC 5 ms 3488 KiB
02_small_03.txt AC 6 ms 3492 KiB
03_mid_1_01.txt AC 7 ms 3492 KiB
03_mid_1_02.txt AC 7 ms 3484 KiB
03_mid_1_03.txt AC 7 ms 3496 KiB
03_mid_1_04.txt AC 7 ms 3508 KiB
03_mid_1_05.txt AC 7 ms 3556 KiB
03_mid_1_06.txt AC 8 ms 3560 KiB
03_mid_1_07.txt AC 7 ms 3620 KiB
03_mid_1_08.txt AC 7 ms 3484 KiB
03_mid_1_09.txt AC 7 ms 3604 KiB
03_mid_1_10.txt AC 7 ms 3564 KiB
03_mid_1_11.txt AC 8 ms 3412 KiB
03_mid_1_12.txt AC 8 ms 3500 KiB
03_mid_1_13.txt AC 7 ms 3488 KiB
03_mid_1_14.txt AC 7 ms 3504 KiB
03_mid_1_15.txt AC 7 ms 3508 KiB
04_mid_2_01.txt AC 6 ms 3500 KiB
04_mid_2_02.txt AC 6 ms 3612 KiB
04_mid_2_03.txt AC 6 ms 3552 KiB
04_mid_2_04.txt AC 6 ms 3568 KiB
04_mid_2_05.txt AC 6 ms 3568 KiB
04_mid_2_06.txt AC 6 ms 3620 KiB
04_mid_2_07.txt AC 6 ms 3552 KiB
04_mid_2_08.txt AC 6 ms 3496 KiB
04_mid_2_09.txt AC 6 ms 3420 KiB
04_mid_2_10.txt AC 6 ms 3484 KiB
04_mid_2_11.txt AC 6 ms 3556 KiB
04_mid_2_12.txt AC 6 ms 3568 KiB
04_mid_2_13.txt AC 6 ms 3532 KiB
04_mid_2_14.txt AC 6 ms 3496 KiB
04_mid_2_15.txt AC 6 ms 3556 KiB
05_mid_3_01.txt AC 6 ms 3564 KiB
05_mid_3_02.txt AC 6 ms 3472 KiB
05_mid_3_03.txt AC 6 ms 3408 KiB
05_mid_3_04.txt AC 6 ms 3560 KiB
05_mid_3_05.txt AC 6 ms 3692 KiB
06_mid_4_01.txt AC 7 ms 3416 KiB
06_mid_4_02.txt AC 7 ms 3504 KiB
06_mid_4_03.txt AC 7 ms 3676 KiB
06_mid_4_04.txt AC 7 ms 3560 KiB
06_mid_4_05.txt AC 7 ms 3412 KiB
07_mid_5_01.txt AC 7 ms 3556 KiB
07_mid_5_02.txt AC 7 ms 3556 KiB
07_mid_5_03.txt AC 7 ms 3556 KiB
07_mid_5_04.txt AC 7 ms 3548 KiB
07_mid_5_05.txt AC 7 ms 3664 KiB
08_max_1_01.txt AC 8 ms 4104 KiB
08_max_1_02.txt AC 33 ms 4048 KiB
08_max_1_03.txt AC 9 ms 4112 KiB
08_max_1_04.txt AC 8 ms 4244 KiB
08_max_1_05.txt AC 30 ms 4172 KiB
08_max_1_06.txt AC 9 ms 4112 KiB
08_max_1_07.txt AC 8 ms 4048 KiB
08_max_1_08.txt AC 21 ms 4112 KiB
08_max_1_09.txt AC 9 ms 4052 KiB
08_max_1_10.txt AC 8 ms 4100 KiB
08_max_1_11.txt AC 31 ms 4040 KiB
08_max_1_12.txt AC 9 ms 4160 KiB
08_max_1_13.txt AC 7 ms 4168 KiB
08_max_1_14.txt AC 31 ms 4048 KiB
08_max_1_15.txt AC 10 ms 4112 KiB
09_max_2_01.txt AC 5 ms 4044 KiB
09_max_2_02.txt AC 6 ms 4096 KiB
09_max_2_03.txt AC 5 ms 4028 KiB
09_max_2_04.txt AC 5 ms 4028 KiB
09_max_2_05.txt AC 7 ms 4052 KiB
09_max_2_06.txt AC 5 ms 4032 KiB
09_max_2_07.txt AC 6 ms 4052 KiB
09_max_2_08.txt AC 6 ms 4048 KiB
09_max_2_09.txt AC 8 ms 4100 KiB
09_max_2_10.txt AC 6 ms 4032 KiB
09_max_2_11.txt AC 6 ms 4112 KiB
09_max_2_12.txt AC 9 ms 4100 KiB
09_max_2_13.txt AC 5 ms 4100 KiB
09_max_2_14.txt AC 6 ms 4056 KiB
09_max_2_15.txt AC 10 ms 4032 KiB
10_max_3_01.txt AC 6 ms 4048 KiB
10_max_3_02.txt AC 6 ms 4028 KiB
10_max_3_03.txt AC 6 ms 4040 KiB
10_max_3_04.txt AC 6 ms 4032 KiB
10_max_3_05.txt AC 6 ms 4036 KiB
11_max_4_01.txt AC 18 ms 4168 KiB
11_max_4_02.txt AC 8 ms 4044 KiB
11_max_4_03.txt AC 14 ms 4044 KiB
11_max_4_04.txt AC 6 ms 4060 KiB
11_max_4_05.txt AC 5 ms 4028 KiB
12_max_5_01.txt AC 17 ms 4080 KiB
12_max_5_02.txt AC 14 ms 4100 KiB
12_max_5_03.txt AC 14 ms 4036 KiB
12_max_5_04.txt AC 13 ms 4084 KiB
12_max_5_05.txt AC 20 ms 4096 KiB