QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#641684 | #9246. Dominating Point | hansue | WA | 0ms | 199456kb | C++14 | 3.4kb | 2024-10-14 22:18:02 | 2024-10-14 22:18:04 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N = 5000;
int n, m;
int g[N + 3][N + 3], f[N + 3][N + 3];
int d[N + 3]; //out degree
char s[N + 3];
struct Node{
int d, i;
Node(){}
Node(int d, int i):d(d),i(i){}
}a[N + 3], b[N + 3];
int cnt;
bool operator<(Node A, Node B){
if(A.d == B.d)
return A.i > B.i;
return A.d > B.d;
}
void swap(Node A, Node B){
Node C = A;
A = B;
B = C;
}
bool check(int u){
for(int v = 1; v <= n; v++)
for(int k = 1; k <= n; k++)
f[u][v] |= g[u][k] && g[k][v];
for(int v = 1; v <= n; v++)
if(v != u && !g[u][v] && !f[u][v])
return false;
return true;
}
bool to1[N + 3];
void pick(){
sort(a + 1, a + n + 1);
cnt = 1;
b[1] = Node(1, a[1].i);
// printf("a[1]:%d %d\n", a[1].d, a[1].i);
for(int i = 2; i <= n && a[i].d == a[1].d; i++){
// printf("a[%2d]:%d %d\n", i, a[i].d, a[i].i);
b[++cnt] = Node(1, a[i].i);
}
if(cnt >= 3){
// printf("out1\n");
if(check(b[1].i) && check(b[2].i) && check(b[3].i))
printf("%d %d %d", b[1].i, b[2].i, b[3].i);
else
printf("NOT FOUND\n");
return;
}
if(cnt == 1){
m = 0;
for(int j = 1; j <= n; j++)
if(g[j][b[1].i])
a[++m] = Node(d[j], j);
// printf("ok1\n");
if(m == 0){
printf("NOT FOUND");
return;
}
sort(a + 1, a + m + 1);
// printf("ok2\n");
b[++cnt] = Node(2, a[1].i);
if(a[2].d == a[1].d){
b[++cnt] = Node(2, a[2].i);
if(check(b[1].i) && check(b[2].i) && check(b[3].i))
printf("%d %d %d", b[1].i, b[2].i, b[3].i);
else
printf("NOT FOUND\n");
return;
}
else {
// printf("ok3\n");
m = 0;
for(int k = 1; k <= n; k++)
if(g[k][b[2].i])
a[++m] = Node(d[k], k);
if(m == 0){
printf("NOT FOUND");
return ;
}
// printf("ok4\n");
sort(a + 1, a + m + 1);
b[++cnt] = Node(3, a[1].i);
if(check(b[1].i) && check(b[2].i) && check(b[3].i))
printf("%d %d %d", b[1].i, b[2].i, b[3].i);
else
printf("NOT FOUND\n");
return ;
}
}
else {
m = 0;
for(int j = 1; j <= n; j++)
if(g[j][b[1].i])
a[++m] = Node(d[j], j);
if(m == 0)
return;
sort(a + 1, a + m + 1);
b[++cnt] = Node(2, a[1].i);
m = 0;
for(int j = 1; j <= n; j++)
if(g[j][b[2].i])
a[++m] = Node(d[j], j);
if(m == 0)
return;
sort(a + 1, a + m + 1);
b[++cnt] = Node(2, a[1].i);
if(check(b[1].i) && check(b[2].i)){
if(check(b[3].i))
printf("%d %d %d", b[1].i, b[2].i, b[3].i);
else
if(check(b[4].i))
printf("%d %d %d", b[1].i, b[2].i, b[4].i);
else
printf("NOT FOUND\n");
return ;
}
else {
printf("NOT FOUND\n");
return ;
}
}
}
bool flag[3 + 3];
int main(){
memset(g, 0, sizeof g);
memset(f, 0, sizeof f);
scanf("%d\n", &n);
for(int i = 1; i <= n; i++){
scanf("%s\n", s);
for(int j = 1; j <= n; j++)
g[i][j] = s[j - 1] - '0';
}
if(n < 3){
printf("NOT FOUND\n");
return 0;
}
// for(int i = 1; i <= n; i++){
// printf("%2d:", i);
// for(int j = 1; j <= n; j++)
// if(g[i][j])
// printf("%d ", j);
// printf("\n");
// }
memset(d, 0, sizeof d);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++)
d[i] += g[i][j];
a[i] = Node(d[i], i);
}
pick();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 199456kb
input:
6 011010 000101 010111 100001 010100 100010
output:
3 1 1
result:
wrong answer Wrong Answer, Duplicate indexes.