QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#676981 | #9246. Dominating Point | H_ZzZ# | TL | 0ms | 3628kb | C++20 | 1.3kb | 2024-10-26 08:08:47 | 2024-10-26 08:08:48 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
int __ = 1,n;
const int N=5050;
bitset<N> a[N],b[N],c[N];
void solve(){
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
char c;cin>>c;
bool now=c-'0';
a[i][j]=now;
b[j][i]=now;
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
bitset<N> t = a[i]&b[j];
// cout<<i<<" "<<j<<endl;
// cout << a[i] << endl;
// cout << b[j] << endl;
// cout << t << endl;
// cout << t.count() << endl;
if(t.count()) c[i][j] = 1;
else c[i][j] = 0;
}
for(int i=1;i<=n;i++)
c[i]=c[i]|a[i];
vector<int>ans;
for(int i=1;i<=n;i++)
{
int cnt=0;
for(int j=1;j<=n;j++)
if(c[i][j]&&i!=j)cnt++;
if(cnt==n - 1)ans.push_back(i);
if(ans.size()>=3)break;
}
if(ans.size()<=2)
{
cout<<"NOT FOUND";
}else
{
for(int x:ans)
cout<<x<<" ";
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
__=1;
//cin >> __;
while (__--){
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3620kb
input:
6 011010 000101 010111 100001 010100 100010
output:
1 3 4
result:
ok OK, Answer correct.
Test #2:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
3 011 001 000
output:
NOT FOUND
result:
ok OK, Answer correct.
Test #3:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
3 010 001 100
output:
1 2 3
result:
ok OK, Answer correct.
Test #4:
score: -100
Time Limit Exceeded
input:
4994 0100001010011001010101110010101000111101111100100001110010000111100000000100110100101000001010100000010010010110110110111010010010100110100000110110111001010111010111010111011001000101001000010001010111110000000100001100000111100011001010010111011100111010101110011000010111101011111110001111110...