結果

問題 No.812 Change of Class
ユーザー akakimidoriakakimidori
提出日時 2019-04-12 21:44:33
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 127 ms / 4,000 ms
コード長 2,267 bytes
コンパイル時間 353 ms
コンパイル使用メモリ 30,464 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-12 06:44:06
合計ジャッジ時間 4,570 ms
ジャッジサーバーID
(参考情報)
judge3 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 60
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<stdio.h>
#include<stdlib.h>
#include<stdint.h>
#include<inttypes.h>
typedef struct directed_edge {
int32_t vertex;
int32_t next;
} graph_edge;
typedef struct directedGraph {
graph_edge *edge;
int32_t *start;
int32_t pointer;
int32_t vertex_num;
int32_t edge_max_size;
} graph;
graph* new_graph (const int vertex_num) {
graph *g = (graph *) calloc (1, sizeof (graph));
g->edge = (graph_edge *) calloc (1, sizeof (graph_edge));
g->start = (int32_t *) calloc (vertex_num, sizeof (int32_t));
g->pointer = 0;
g->vertex_num = vertex_num;
g->edge_max_size = 1;
for (int32_t i = 0; i < vertex_num; ++i) {
g->start[i] = -1;
}
return g;
}
void add_edge (graph *g, int32_t from, int32_t to) {
if (g->pointer == g->edge_max_size) {
g->edge_max_size *= 2;
g->edge = (graph_edge *) realloc (g->edge, sizeof (graph_edge) * g->edge_max_size);
}
g->edge[g->pointer] = (graph_edge) {to, g->start[from]};
g->start[from] = g->pointer++;
}
int32_t BFS_graph (graph *g, int32_t src, int32_t *res) {
int32_t *q = (int32_t *) calloc (g->vertex_num, sizeof (int32_t));
uint8_t *used = (uint8_t *) calloc (g->vertex_num, sizeof (uint8_t));
int32_t *d = (int32_t *) calloc (g->vertex_num, sizeof (int32_t));
int32_t front = 0;
int32_t last = 0;
used[src] = 1;
q[last++] = src;
while (front < last) {
const int32_t v = q[front++];
for (int32_t p = g->start[v]; p != -1; p = g->edge[p].next) {
const int32_t u = g->edge[p].vertex;
if (!used[u]) {
used[u] = 1;
q[last++] = u;
d[u] = d[v] + 1;
}
}
}
*res = d[q[last - 1]];
free(q);
free(used);
free (d);
return last;
}
typedef int32_t i32;
void run (void) {
i32 n, m;
scanf ("%" SCNi32 "%" SCNi32, &n, &m);
graph *g = new_graph (n);
while (m--) {
i32 a, b;
scanf ("%" SCNi32 "%" SCNi32, &a, &b);
a--;
b--;
add_edge (g, a, b);
add_edge (g, b, a);
}
i32 q;
scanf ("%" SCNi32, &q);
while (q--) {
i32 a;
scanf ("%" SCNi32, &a);
a--;
i32 dd = 0;
i32 ans = BFS_graph (g, a, &dd) - 1;
i32 d = 1;
i32 k = 0;
while (d < dd) {
d *= 2;
k++;
}
printf ("%" PRIi32 " %" PRIi32 "\n", ans, k);
}
}
int main (void) {
run ();
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0