ソースコード 拡げる

Copy
```#include <stdio.h>
#include <stdlib.h>
#define graph_valtype int

typedef struct {
int a;
int b;
int w;
}edge;

typedef struct graph_edge_sub graph_edge;

typedef struct {
int num;
int next_num;
graph_edge *next;
int prev_num;
}graph_vertex_sub;

struct graph_edge_sub{
graph_vertex_sub *v;
int w;
graph_edge *next;
};

typedef struct graph_v_sub graph_vertex;

struct graph_v_sub{
int num;
graph_valtype val;
int next_num;
graph_vertex **next;
int *next_weight;
int prev_num;
graph_vertex **prev;
int *prev_weight;
};

typedef struct {
int N;
graph_vertex_sub **v_s;
graph_vertex **v;
}graph;

//頂点数N, 各頂点の初期値ini_valのグラフを作る
graph *make_graph(int N, graph_valtype ini_val){
int i;
graph *g = (graph *)malloc(sizeof(graph));
g->N = N;
g->v_s = (graph_vertex_sub **)malloc(sizeof(graph_vertex_sub *) * N);
g->v = (graph_vertex **)malloc(sizeof(graph_vertex *) * N);
for(i = 0; i < N; i++){
(g->v_s)[i] = (graph_vertex_sub *)malloc(sizeof(graph_vertex_sub));
(g->v_s)[i]->num = i;
(g->v_s)[i]->next_num = 0;
(g->v_s)[i]->next = NULL;
(g->v_s)[i]->prev_num = 0;
(g->v)[i] = (graph_vertex *)malloc(sizeof(graph_vertex));
(g->v)[i]->num = i;
(g->v)[i]->val = ini_val;
(g->v)[i]->next_num = 0;
(g->v)[i]->next = NULL;
(g->v)[i]->next_weight = NULL;
(g->v)[i]->prev_num = 0;
(g->v)[i]->prev = NULL;
(g->v)[i]->prev_weight = NULL;
}
return g;
}

//グラフgの頂点aから頂点bに重みwの有向辺を張る (0 <= a, b <= N - 1)
void set_edge_graph(int a, int b, int w, graph *g){
graph_edge *new1 = (graph_edge *)malloc(sizeof(graph_edge));
new1->v = (g->v_s)[b];
new1->w = w;
new1->next = (g->v_s)[a]->next;
(g->v_s)[a]->next = new1;
(g->v_s)[a]->next_num++;
(g->v_s)[b]->prev_num++;
}

//set_edge_graph後に呼び出す
void build_graph(graph *g){
int i;
graph_vertex_sub **v_s = g->v_s;
graph_vertex **v = g->v;
graph_vertex *nowv;
graph_edge *nowe;
for(i = 0; i < g->N; i++){
v[i]->next = (graph_vertex **)malloc(sizeof(graph_vertex *) * v_s[i]->next_num);
v[i]->next_weight = (int *)malloc(sizeof(int) * v_s[i]->next_num);
v[i]->prev = (graph_vertex **)malloc(sizeof(graph_vertex *) * v_s[i]->prev_num);
v[i]->prev_weight = (int *)malloc(sizeof(int) * v_s[i]->prev_num);
}
for(i = 0; i < g->N; i++){
nowv = v[i];
for(nowe = v_s[i]->next; nowe != NULL; nowe = nowe->next){
(nowv->next)[nowv->next_num] = v[nowe->v->num];
(nowv->next_weight)[nowv->next_num] = nowe->w;
nowv->next_num++;
(v[nowe->v->num]->prev)[v[nowe->v->num]->prev_num] = nowv;
(v[nowe->v->num]->prev_weight)[v[nowe->v->num]->prev_num] = nowe->w;
v[nowe->v->num]->prev_num++;
}
}
}

char *s;
int *is_used;
graph *g;

int solve(int a, int b, int w){
int i;
if(is_used[w] > 0){
return 2 - is_used[w];
}
is_used[w] = 1;
graph_vertex *nowv = g->v[b];
for(i = 0; i < nowv->next_num; i++){
if(s[a] != s[nowv->next[i]->num]){
if(solve(b, nowv->next[i]->num, nowv->next_weight[i]) == 1){
return 1;
}
}
}
is_used[w] = 2;
return 0;
}

int main(){
int N, M, a, b, i, j, k;
scanf("%d%d", &N, &M);
s = (char *)malloc(sizeof(char) * N);
scanf("%s", s);
edge *es = (edge *)malloc(sizeof(edge) * 2 * M);
g = make_graph(N, 0);
for(i = 0; i < M; i++){
scanf("%d%d", &a, &b);
es[2 * i].a = a - 1;
es[2 * i].b = b - 1;
es[2 * i + 1].a = b - 1;
es[2 * i + 1].b = a - 1;
set_edge_graph(a - 1, b - 1, 2 * i, g);
set_edge_graph(b - 1, a - 1, 2 * i + 1, g);
}
build_graph(g);
is_used = (int *)malloc(sizeof(int) * 2 * M);
for(i = 0; i < 2 * M; i++){
is_used[i] = 0;
}
for(i = 0; i < 2 * M; i++){
if(solve(es[i].a, es[i].b, i) == 1){
printf("Yes\n");
return 0;
}
}
printf("No\n");
return 0;
}```

#### 提出情報

提出日時 2018-09-19 06:57:12+0900 C - ABland Yard abc050 C (GCC 5.4.1) 900 3899 Byte AC 238 ms 63744 KB

#### コンパイルエラー

```./Main.c: In function ‘main’:
./Main.c:132:2: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &M);
^
./Main.c:134:2: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", s);
^
./Main.c:138:3: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a, &b);
^
```

#### テストケース

セット名 得点 / 配点 テストケース
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
All 900 / 900 sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt, test_29.txt, test_30.txt, test_31.txt, test_32.txt, test_33.txt, test_34.txt, test_35.txt, test_36.txt, test_37.txt, test_38.txt, test_39.txt, test_40.txt, test_41.txt, test_42.txt, test_43.txt, test_44.txt, test_45.txt, test_46.txt, test_47.txt, test_48.txt, test_49.txt, test_50.txt, test_51.txt, test_52.txt, test_53.txt, test_54.txt, test_55.txt
ケース名 結果 実行時間 メモリ
sample_01.txt 1 ms 128 KB
sample_02.txt 1 ms 128 KB
sample_03.txt 1 ms 128 KB
sample_04.txt 1 ms 128 KB
test_01.txt 161 ms 49408 KB
test_02.txt 238 ms 54272 KB
test_03.txt 82 ms 31232 KB
test_04.txt 172 ms 51968 KB
test_05.txt 156 ms 41472 KB
test_06.txt 86 ms 31744 KB
test_07.txt 42 ms 17920 KB
test_08.txt 85 ms 33152 KB
test_09.txt 72 ms 24448 KB
test_10.txt 46 ms 17024 KB
test_11.txt 189 ms 55680 KB
test_12.txt 186 ms 54912 KB
test_13.txt 104 ms 33408 KB
test_14.txt 179 ms 50688 KB
test_15.txt 154 ms 39168 KB
test_16.txt 41 ms 14720 KB
test_17.txt 55 ms 20352 KB
test_18.txt 41 ms 15232 KB
test_19.txt 74 ms 26240 KB
test_20.txt 62 ms 20992 KB
test_21.txt 59 ms 18176 KB
test_22.txt 158 ms 47616 KB
test_23.txt 95 ms 33792 KB
test_24.txt 149 ms 40960 KB
test_25.txt 101 ms 29952 KB
test_26.txt 210 ms 59264 KB
test_27.txt 122 ms 39936 KB
test_28.txt 67 ms 32640 KB
test_29.txt 111 ms 34816 KB
test_30.txt 25 ms 8704 KB
test_31.txt 162 ms 52736 KB
test_32.txt 142 ms 46464 KB
test_33.txt 169 ms 46592 KB
test_34.txt 36 ms 13952 KB
test_35.txt 220 ms 63744 KB
test_36.txt 1 ms 128 KB
test_37.txt 1 ms 256 KB
test_38.txt 1 ms 128 KB
test_39.txt 1 ms 128 KB
test_40.txt 1 ms 256 KB
test_41.txt 1 ms 128 KB
test_42.txt 1 ms 128 KB
test_43.txt 1 ms 128 KB
test_44.txt 1 ms 256 KB
test_45.txt 1 ms 128 KB
test_46.txt 1 ms 128 KB
test_47.txt 1 ms 128 KB
test_48.txt 1 ms 256 KB
test_49.txt 1 ms 128 KB
test_50.txt 1 ms 128 KB
test_51.txt 1 ms 128 KB
test_52.txt 1 ms 256 KB
test_53.txt 1 ms 128 KB
test_54.txt 1 ms 128 KB
test_55.txt 1 ms 128 KB