oj.uz

Submission #28792

# Submission time Handle Problem Language Result Execution time Memory
28792 2017-07-17T08:12:07 Z kajebiii Play Onwards (FXCUP2_onward) C++14
1 / 1
 9 ms 2300 KB 
#include <stdio.h>
#include <bits/stdc++.h>
 
using namespace std;
 
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi; typedef pair<ll, int> pli; typedef pair<ll, pi> plp;
typedef tuple<int, int, int> ti; typedef tuple<ll, int, int> tli;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;
 
const int MAX_N = 2e2 + 10;
 
int N, K; char S[MAX_N][50]; int sN[MAX_N], C[MAX_N];
vector<int> Ed[MAX_N];
bool vis[MAX_N];
bool isCon(int i, int j) {
	for(int a=0; a+K-1<sN[i]; a++) for(int b=0; b+K-1<sN[j]; b++) {
		bool isCan = true;
		for(int k=0; k<K; k++) if(S[i][a+k] != S[j][b+k]) {isCan = false; break;}
		if(isCan) return true;
	}
	return false;
}
bool impos = false;
void dfs(int v, int c) {
	vis[v] = true;
	C[v] = c;
	for(int w : Ed[v]) {
		if(vis[w] == true) {
			if(C[w] + C[v] != 1) {impos = true;}
		}else dfs(w, 1-C[v]);
	}
}
int main() {
	cin >> N >> K;
	for(int i=0; i<N; i++) scanf("%s", S[i]), sN[i] = strlen(S[i]);
	for(int i=0; i<N; i++) for(int j=i+1; j<N; j++) {
		if(isCon(i, j)) {
//			printf("%d %d\n", i, j);
			Ed[i].push_back(j), Ed[j].push_back(i);
		}
	}
	for(int i=0; i<N; i++) if(vis[i] == false) {
		dfs(i, 0);
	}
	if(impos) puts("No");
	else {
		puts("Yes");
		int cnt[2] ={0, 0};
		for(int i=0; i<N; i++) cnt[C[i]]++;
		if(cnt[0] == N || cnt[1] == N) {
			for(int i=0; i<N-1; i++) printf("%d\n", 1);
			for(int i=N-1; i<N; i++) printf("%d\n", 2);
		}else for(int i=0; i<N; i++) printf("%d\n", C[i] + 1);
	}
	return 0;
}

Compilation message

onward.cpp: In function 'int main()':
onward.cpp:41:64: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<N; i++) scanf("%s", S[i]), sN[i] = strlen(S[i]);
                                                                ^

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2036 KB Output is correct
2 Correct 0 ms 2036 KB Output is correct
3 Correct 0 ms 2036 KB Output is correct
4 Correct 0 ms 2036 KB Output is correct
5 Correct 0 ms 2300 KB Output is correct
6 Correct 0 ms 2300 KB Output is correct
7 Correct 6 ms 2036 KB Output is correct
8 Correct 6 ms 2036 KB Output is correct
9 Correct 6 ms 2036 KB Output is correct
10 Correct 3 ms 2036 KB Output is correct
11 Correct 0 ms 2036 KB Output is correct
12 Correct 6 ms 2036 KB Output is correct
13 Correct 9 ms 2036 KB Output is correct
14 Correct 3 ms 2036 KB Output is correct
15 Correct 0 ms 2036 KB Output is correct
16 Correct 0 ms 2036 KB Output is correct
17 Correct 0 ms 2036 KB Output is correct
18 Correct 0 ms 2036 KB Output is correct
19 Correct 3 ms 2036 KB Output is correct
20 Correct 3 ms 2036 KB Output is correct
21 Correct 3 ms 2036 KB Output is correct