QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#641706#9246. Dominating PointhansueRE 11ms199488kbC++143.9kb2024-10-14 22:37:192024-10-14 22:37:19

Judging History

你现在查看的是最新测评结果

  • [2024-11-22 18:38:25]
  • hack成功,自动添加数据
  • (/hack/1238)
  • [2024-10-14 22:37:19]
  • 评测
  • 测评结果:RE
  • 用时:11ms
  • 内存:199488kb
  • [2024-10-14 22:37:19]
  • 提交

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...

output:


result: