oj.uz

Submission #28364

# Submission time Handle Problem Language Result Execution time Memory
28364 2017-07-16T05:01:33 Z 뚜룹뚜룹뚜룹뚜스~><(#1151, chan492811) Play Onwards (FXCUP2_onward) C++
0 / 1
 16 ms 1996 KB 
#include <cstdio>
#include <cstring>
#include <vector>
#define MAX_V 410
using namespace std;

int n, m, res = 1;
char arr[MAX_V][21];
int carr[MAX_V];
bool visit[MAX_V];
vector <int> vs, G[MAX_V], rG[MAX_V];

bool iscan(int a, int s){
	int i, j, k, na, ns, cnt;
	na = strlen(arr[a]);
	ns = strlen(arr[s]);
	for(i = 0; i <= na - m; i++){
		for(j = 0; j <= ns - m; j++){
			cnt = 0;
			for(k = 0; k < m; k++){ if(arr[a][i + k] == arr[s][j + k]) cnt++; }
			if(cnt == m) return 1;
		}
	}
	return 0;
}
int V_Trans(int a){
	if(a < 0) return -a + n;
	return a;
}
void add_edge(int from, int to){
	from = V_Trans(from);
	to = V_Trans(to);
	G[from].push_back(to);
	rG[to].push_back(from);
}
void DFS(int a){
	visit[a] = 1;
	for(int i = 0; i < G[a].size(); i++){
		if(!visit[G[a][i]]) DFS(G[a][i]);
	}
	vs.push_back(a);
}
void rDFS(int a, int s){
	visit[a] = 1;
	carr[a] = s;
	for(int i = 0; i < rG[a].size(); i++){
		if(!visit[rG[a][i]]) rDFS(rG[a][i], s);
	}
}
void SCC(){
	int s = 1;
	for(int i = 1; i <= 2 * n; i++) if(!visit[i]) DFS(i);
	memset(visit, 0, sizeof(visit));
	for(int i = vs.size() - 1; i >= 0; i--) if(!visit[vs[i]]) rDFS(vs[i], s++);
}
int main(){
	int i, j, a, s;
	scanf("%d %d", &n, &m);
	for(i = 1; i <= n; i++) scanf("%s", arr[i]);
	for(i = 1; i <= n; i++){
		for(j = i + 1; j <= n; j++){
			if(iscan(i, j)) add_edge(-i, j), add_edge(-j, i), add_edge(i, -j), add_edge(j, -i);
		}
	}
	SCC();
	for(i = 1; i <= n; i++){
		if(carr[i] == carr[n + i]) res = 0;
	}
	if(!res){ printf("No"); return 0; }
	printf("Yes\n");
	if(res){
		for(i = 1; i <= n; i++){
			if(carr[i] > carr[n + i]) printf("1\n");
			else printf("2\n");
		}
	}
	return 0;
}

Compilation message

onward.cpp: In function 'void DFS(int)':
onward.cpp:38:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < G[a].size(); i++){
                   ^
onward.cpp: In function 'void rDFS(int, int)':
onward.cpp:46:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < rG[a].size(); i++){
                   ^
onward.cpp: In function 'int main()':
onward.cpp:57:12: warning: unused variable 'a' [-Wunused-variable]
  int i, j, a, s;
            ^
onward.cpp:57:15: warning: unused variable 's' [-Wunused-variable]
  int i, j, a, s;
               ^
onward.cpp:58:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
                        ^
onward.cpp:59:45: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i = 1; i <= n; i++) scanf("%s", arr[i]);
                                             ^

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1204 KB Output is correct
2 Correct 0 ms 1204 KB Output is correct
3 Correct 0 ms 1204 KB Output is correct
4 Correct 0 ms 1204 KB Output is correct
5 Correct 3 ms 1996 KB Output is correct
6 Correct 3 ms 1996 KB Output is correct
7 Correct 13 ms 1204 KB Output is correct
8 Correct 13 ms 1204 KB Output is correct
9 Correct 13 ms 1204 KB Output is correct
10 Correct 16 ms 1204 KB Output is correct
11 Incorrect 0 ms 1204 KB Output isn't correct
12 Halted 0 ms 0 KB -