QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#641706 | #9246. Dominating Point | hansue | RE | 11ms | 199488kb | C++14 | 3.9kb | 2024-10-14 22:37:19 | 2024-10-14 22:37:19 |
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);
// for(int i = 1; i <= n; i++)
// printf("a[%2d]:%2d %2d\n", i, a[i].d, a[i].i);
// printf("\n");
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){
// printf("ok1\n");
m = 0;
for(int j = 1; j <= n; j++)
if(g[j][b[1].i])
a[++m] = Node(d[j], j);
if(m == 0){
printf("NOT FOUND");
return;
}
sort(a + 1, a + m + 1);
b[++cnt] = Node(2, a[1].i);
if(m < 2 || a[2].d != a[1].d)
{
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 ;
}
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
{
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 {
m = 0;
for(int j = 1; j <= n; j++)
if(g[j][b[1].i])
a[++m] = Node(d[j], j);
if(m == 0){
printf("NOT FOUND");
return;
}
sort(a + 1, a + m + 1);
if(a[1].i == b[2].i){
printf("here1\n");
if(m > 1){
b[++cnt] = Node(2, a[2].i);
}
else {
printf("NOT FOUND");
return;
}
}
else
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){
printf("NOT FOUND");
return;
}
sort(a + 1, a + m + 1);
if(a[1].i == b[1].i){
printf("here2\n");
if(m > 1){
b[++cnt] = Node(2, a[2].i);
}
else {
printf("NOT FOUND");
return;
}
}
else
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: 100
Accepted
time: 0ms
memory: 199488kb
input:
6 011010 000101 010111 100001 010100 100010
output:
3 1 6
result:
ok OK, Answer correct.
Test #2:
score: 0
Accepted
time: 11ms
memory: 199420kb
input:
3 011 001 000
output:
NOT FOUND
result:
ok OK, Answer correct.
Test #3:
score: 0
Accepted
time: 4ms
memory: 199472kb
input:
3 010 001 100
output:
3 2 1
result:
ok OK, Answer correct.
Test #4:
score: -100
Runtime Error
input:
4994 0100001010011001010101110010101000111101111100100001110010000111100000000100110100101000001010100000010010010110110110111010010010100110100000110110111001010111010111010111011001000101001000010001010111110000000100001100000111100011001010010111011100111010101110011000010111101011111110001111110...