제출 #728894

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
728894		WonderfulWhale	Genetics (BOI18_genetics)	C++17	27 / 100	2040 ms	73232 KiB

genetics

#include<bits/stdc++.h>
using namespace std;

#define pb push_back
#define st first
#define nd second
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

string tab[4109];
bool vis[4109];

queue<int> Q;
int dp[4109][4109];

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	memset(dp, -1, sizeof(dp));

	int n, m, K;
	cin >> n >> m >> K;
	for(int i=1;i<=n;i++) cin >> tab[i];
	vector<int> v;
	for(int i=1;i<=n;i++) v.pb(i);
	random_shuffle(all(v));
	vis[1] = true;
	Q.push(1);
	while(true) {
		int x = Q.front();
		Q.pop();
		bool ans = true;
		for(int i=0;i<n;i++) {
			if(v[i]==x) continue;
			int cnt = dp[v[i]][x];
			if(cnt==-1) {
				cnt = 0;
				for(int j=0;j<m;j++) {
					if(tab[x][j]!=tab[v[i]][j]) cnt++;
				}
			}
			dp[v[i]][x] = dp[x][v[i]] = cnt;
			if(cnt==K) {
				if(!vis[v[i]]) {
					vis[v[i]] = true;
					Q.push(v[i]);
				}
			} else {
				vis[v[i]] = true;
				ans = false;
			}
		}
		if(ans) {
			cout << x << "\n";
			return 0;
		}
	}
}

• Subtask 1: 27 / 27
• Subtask 2: 0 / 19
• Subtask 3: 0 / 28
• Subtask 4: 0 / 26