QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#641684#9246. Dominating PointhansueWA 0ms199456kbC++143.4kb2024-10-14 22:18:022024-10-14 22:18:04

Judging History

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

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

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.