oj.uz

답안 #28770

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
28770 2017-07-17T07:27:57 Z sgc109 Play Onwards (FXCUP2_onward) C++11
1 / 1
 33 ms 3164 KB 
#include <bits/stdc++.h>
#define fastio() ios_base::sync_with_stdio(false),cin.tie(NULL)
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;

class SCC{
	vector<vector<int> > G;
	vector<int> sccId, order;
	int visitCnt, sccCnt, size;
	stack<int> stck;
public:
	SCC(){}
	SCC(vector<int>* graph, int size){
		this->size = size;
		G = vector<vector<int> >(size);
		for(int i = 0 ; i < size; i++) G[i] = graph[i];
		sccId = vector<int>(size, -1);
		order = vector<int>(size, -1);
		visitCnt = sccCnt = 0;
		for(int i = 0 ; i < size; i++) {
			if(order[i] == -1) dfs(i);
		}
		for(int i = 0 ; i < size; i++) sccId[i] = sccCnt - sccId[i] - 1;
	}
	int dfs(int cur){
		stck.push(cur);
		int ret = order[cur] = visitCnt++;
		for(int next : G[cur]){
			if(order[next] == -1) ret = min(ret, dfs(next));
			else if(sccId[next] == -1) ret = min(ret, order[next]);
		}
		if(order[cur] == ret){
			while(1){
				int top = stck.top();
				stck.pop();
				sccId[top] = sccCnt;
				if(top == cur) break;
			}
			sccCnt++;
		}
		return ret;
	}
	vector<vector<int> > getCompGraph(){
		vector<vector<int> > compG = vector<vector<int> >(sccCnt);
		for(int cur = 0 ; cur < size; cur++){
			for(int next : G[cur]){
				if(sccId[cur] == sccId[next]) continue;
				compG[sccId[cur]].push_back(sccId[next]);
			}
		}
		sort(compG.begin(), compG.end());
		for(int i = 0; i < sccCnt; i++) {
			compG[i].erase(unique(compG[i].begin(), compG[i].end()), compG[i].end());
		}
		return compG;
	}
	vector<int> getSccId(){
		return sccId;
	}
	int getSccCnt(){
		return sccCnt;
	}
};
class TwoSAT{
	SCC scc;
	vector<int> ans;
	bool isPossible;
public:
	TwoSAT(vector<int>* graph, int size){
		scc = SCC(graph, size);
		vector<int> sccId = scc.getSccId();
		isPossible = true;
		for(int i = 0 ; i < size; i+=2){
			if(sccId[i] == sccId[i+1]) isPossible = false;
		}
		if(isPossible){
			ans = vector<int>(size / 2, -1);
			vector<pair<int,int> > sorted;
			for(int i = 0 ; i < size; i++){
				sorted.push_back({sccId[i], i});
			}
			sort(sorted.begin(), sorted.end());
			for(auto p : sorted){
				int num = p.second;
				int isFalse = num&1;
				if(ans[num / 2] != -1) continue;
				ans[num / 2] = isFalse;
			}
		}
	}
	vector<int> getAns(){
		if(!isPossible) return vector<int>();
		return ans;
	}
};
int NOT(int x){
	return x^1;
}
int TRANS(int x){
	return x*2;
}

int N,K;
vector<int> G[500];
string words[203];
int rev[203][203];
int dp[23][23];
int main() {
	fastio();
	cin >> N >> K;
	for(int i = 0 ; i < N; i++) cin >> words[i];
	for(int i = 0 ; i < N; i++){
		for(int j = i + 1; j < N; j++){
			int maxLen = 0;
			memset(dp,0,sizeof(dp));
			for(int a = 1; a <= (int)words[i].size(); a++){
				for(int b = 1; b <= (int)words[j].size(); b++){
					char c1 = words[i][a - 1];
					char c2 = words[j][b - 1];
					if(c1 == c2) dp[a][b] = dp[a - 1][b - 1] + 1;
					else dp[a][b] = 0;
					maxLen = max(maxLen, dp[a][b]);
				}
			}
			if(maxLen >= K) {
				G[TRANS(i)].push_back(NOT(TRANS(j)));
				G[NOT(TRANS(i))].push_back(TRANS(j));
				G[TRANS(j)].push_back(NOT(TRANS(i)));
				G[NOT(TRANS(j))].push_back(TRANS(i));
				rev[i][j] = rev[j][i] = 1;
			}
		}
	}
	
	TwoSAT sat(G, 2*N);
	vector<int> ans = sat.getAns();
	if((int)ans.size() == 0) return !printf("No\n");
	
	cout << "Yes" << endl;
	int allSame = 1;
	for(int i = 0 ; i < N - 1; i++) if(ans[i] != ans[i+1]) allSame = 0;
	if(!allSame) for(int i = 0 ; i < N; i++) cout << ans[i] + 1 << endl;
	else {
		for(int i = 0 ; i < N; i++){
			int ok = 1;
			ans[i] = !ans[i];
			for(int j = 0 ; j < N; j++){
				if(i == j) continue;
				if(rev[i][j] && ans[i] == ans[j]) ok = 0;
			}
			if(ok){
				for(int i = 0 ; i < N; i++) cout << ans[i] + 1 << endl;
				return 0;		
			}
			ans[i] = !ans[i];
		}
	}

	return 0;
}

Subtask #1
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2372 KB Output is correct
2 Correct 0 ms 2372 KB Output is correct
3 Correct 0 ms 2372 KB Output is correct
4 Correct 0 ms 2372 KB Output is correct
5 Correct 16 ms 3164 KB Output is correct
6 Correct 3 ms 3032 KB Output is correct
7 Correct 9 ms 2372 KB Output is correct
8 Correct 9 ms 2372 KB Output is correct
9 Correct 6 ms 2372 KB Output is correct
10 Correct 6 ms 2372 KB Output is correct
11 Correct 33 ms 2372 KB Output is correct
12 Correct 19 ms 2372 KB Output is correct
13 Correct 16 ms 2372 KB Output is correct
14 Correct 23 ms 2372 KB Output is correct
15 Correct 0 ms 2372 KB Output is correct
16 Correct 0 ms 2372 KB Output is correct
17 Correct 0 ms 2372 KB Output is correct
18 Correct 6 ms 2372 KB Output is correct
19 Correct 6 ms 2372 KB Output is correct
20 Correct 9 ms 2372 KB Output is correct
21 Correct 9 ms 2372 KB Output is correct