| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 28263 | 볼빨간 승관이 (#68) | Play Onwards (FXCUP2_onward) | C++98 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
int n, k;
char str[210][25];
long long B = 255;
bool connect(int a, int b) {
std::unordered_set<long long> set;
for (int i = 0; str[a][i + k -1] != '\0'; i++) {
long long h = 0;
for (int j = 0; j < k; j++) {
h *= B;
h += str[a][i+j];
}
set.insert(h);
}
for (int i = 0; str[b][i + k -1] != '\0'; i++) {
long long h = 0;
for (int j = 0; j < k; j++) {
h *= B;
h += str[b][i+j];
}
if (set.count(h))return true;
}
return false;
}
using std::vector;
vector<int> G[210];
int color[210];
bool dfs(int idx) {
for (int to : G[idx]) {
if (color[to] == 0) {
color[to] = -color[idx];
if (!dfs(to)) {
return false;
}
}
else if (color[to] == color[idx]) {
return false;
}
}
return true;
}
int main() {
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i++) {
scanf("%s", str[i]);
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (connect(i, j)) {
G[i].push_back(j);
G[j].push_back(i);
}
}
}
for (int i = 0; i < n; i++) {
if (color[i] == 0) {
color[i] = 1;
if (!dfs(i)) {
printf("No");
return 0;
}
}
}
printf("Yes\n");
for (int i = 0; i < n; i++) {
if (color[i] == -1) {
printf("2\n");
}
else {
printf("1\n");
}
}
}