結果
問題 | No.812 Change of Class |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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;}