QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#1052#671062#9246. Dominating PointEvanEvanFailed.2024-10-24 10:42:502024-10-24 10:42:50

Details

Extra Test:

Accepted
time: 0ms
memory: 3720kb

input:

6
011010
000101
010111
100001
010100
100010

output:

1 3 4

result:

ok OK, Answer correct.

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#671062#9246. Dominating PointEvanAC ✓677ms7144kbC++17973b2024-10-24 10:32:492024-11-22 18:46:56

answer

#include<bits/stdc++.h>
using namespace std;
#define N 5010
bitset<N> s[N],tmp;
int n,cnt[N];
void solve()
{
    scanf("%d",&n);
    int i,j,k;
    for(i=1;i<=n;i++)
    {
        getchar();
        for(j=1;j<=n;j++)
        {
            k=getchar();
            k=k-'0';
            s[i][j]=k;
            if(i==j){s[i][j]=1;}
        }
        cnt[i]=s[i].count();
    }
    vector<int> ans;
    for(i=1;i<=n&&ans.size()<3;i++)
    {
        if(cnt[i]==n){ans.push_back(i);continue;}
        tmp=s[i];
        int tt=cnt[i];
        for(j=1;j<=n;j++)
        {
            if(s[i][j]){tt+=cnt[j];}
        }
        if(tt<=n){continue;}
        for(j=1;j<=n;j++)
        {
            if(s[i][j]){tmp|=s[j];}
        }
        if(tmp.count()==n){ans.push_back(i);}
    }
    if(ans.size()==3){printf("%d %d %d\n",ans[0],ans[1],ans[2]);}
    else{printf(" NOT FOUND\n");}
}
int main()
{
    int t=1;
    while(t--){solve();}
}