QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#1042#555744#9246. Dominating PointmoosyJZYZFailed.2024-10-22 10:08:502024-10-22 10:08:50

Details

Extra Test:

Invalid Input

input:

4
0010
1000
0001
0100

output:


result:

FAIL Validator must end with readEof call.

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#555744#9246. Dominating PointJZYZ#AC ✓230ms126648kbC++141.1kb2024-09-10 09:00:552024-11-22 18:42:52

answer

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 5010;
int n, cnt[N][N], deg[N], nd[N];
char mp[N][N];
bool vis[N];
int main() {
	set< int > s;
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++ ) {
		scanf("%s", mp[i] + 1);
		for(int j = 1; j <= n; j ++ ) {
			if(mp[i][j] == '1') cnt[i][j] = 1, deg[i] ++;
		}
		nd[i] = deg[i];
		if(deg[i] > 0) s.insert(i);
	}
	bool ff = 1; vector< int > ans;
	for(int i = 1; i <= 3; i ++ ) {
		if(s.empty()) {
			ff = 0;
			break;
		}
		int maxn = 0, idx = -1;
		for(auto v : s) {
			if(deg[v] > maxn) maxn = deg[v], idx = v;
		}
		ans.pb(idx);
        // 把所有不能到 idx 的点删掉 
        for(int j = 1; j <= n; j ++ ) {
        	bool flag = 1;
        	for(int k = 1; k <= n; k ++ ) {
        		if(cnt[j][k] && !cnt[idx][k]) {
        			flag = 0;
        			break;
				}
			}
			if(flag) {
				if(s.find(j) != s.end()) s.erase(j);
			}
		} 
	}
	if(ff) {
		for(int i = 1; i <= 3; i ++ ) printf("%d ", ans[i - 1]);
	}
	else puts("NOT FOUND");
	return 0;
}