結果
問題 | No.812 Change of Class |
ユーザー |
|
提出日時 | 2019-04-12 22:26:40 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 100 ms / 4,000 ms |
コード長 | 2,498 bytes |
コンパイル時間 | 1,927 ms |
コンパイル使用メモリ | 89,912 KB |
実行使用メモリ | 7,512 KB |
最終ジャッジ日時 | 2024-06-12 19:09:40 |
合計ジャッジ時間 | 5,572 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 60 |
コンパイルメッセージ
main.cpp: In function ‘int main(int, char**)’: main.cpp:103:12: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 103 | scanf("%d%d", &p, &q); | ~~~~~^~~~~~~~~~~~~~~~ main.cpp:115:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 115 | scanf("%d", &q); | ~~~~~^~~~~~~~~~ main.cpp:117:12: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 117 | scanf("%d", &p); | ~~~~~^~~~~~~~~~
ソースコード
#include <assert.h>#include <ctype.h>#include <float.h>#include <limits.h>#include <math.h>#include <stdio.h>#include <stdlib.h>#include <string.h>#include <sys/types.h>#include <algorithm>#include <bitset>#include <complex>#include <iostream>#include <list>#include <map>#include <numeric>#include <queue>#include <set>#include <sstream>#include <stack>#include <string>#include <unordered_map>#include <unordered_set>#include <vector>using namespace std;#define SZ(a) (int)(a).size()#define FOR(i,a,b) for (int i=(a); i<=(b); ++i)#define REP(i,n) for (int i=0; i<(n); ++i)#define ALL(c) c.begin(), c.end()#define CLR(c,n) memset(c, n, sizeof(c))#define MCPY(d, s) memcpy(d, s, sizeof(d))#define TR(it, c) for (auto it = c.begin();it != c.end(); ++it)#define CONTAIN(it, c) (c.find(it) != c.end())typedef vector<int> VI;typedef pair<int, int> PII;template <class T> void checkmin(T &a, T b) { if (b<a) a=b; }template <class T> void checkmax(T &a, T b) { if (b>a) a=b; }typedef long long LL;const int INF=0x3F3F3F3F;const int N=100000, M=N*2;int n, m;int head[N], dst[M], nxt[M];int deg[N];int c[N], ccnt[N], nc;int q[N], d[N];void add_edge(int u, int v, int id) {dst[id] = v;nxt[id] = head[u];head[u] = id;++deg[u];}void fill(int root) {int qa = 0, qe = 0;q[qe++] = root;c[root] = nc;while (qa < qe) {root = q[qa++];for (int i = head[root]; i >= 0; i = nxt[i]) {int d = dst[i];if (c[d] >= 0) continue;c[d] = nc;q[qe++] = d;}}ccnt[nc] = qe;}int bfs(int root) {CLR(d, -1);d[root] = 0;int qa = 0, qe = 0;q[qe++] = root;if (head[root] < 0) return 0;while (qa < qe) {root = q[qa++];for (int i = head[root]; i >= 0; i = nxt[i]) {int dest = dst[i];if (d[dest] >= 0) continue;d[dest] = d[root] + 1;q[qe++] = dest;}}int dist = d[q[qe-1]], day = 0, md = 1;while (md < dist) {md *= 2;++day;}return day;}int main(int argc, char *argv[]) {int p, q;while (scanf("%d%d", &n, &m) == 2) {CLR(head, -1);CLR(deg, 0);REP(i, m) {scanf("%d%d", &p, &q);--p; --q;add_edge(p, q, i*2);add_edge(q, p, i*2+1);}CLR(c, -1);CLR(ccnt, 0);nc = 0;REP(i, n) if(c[i] == -1) {fill(i);++nc;}scanf("%d", &q);REP(i, q) {scanf("%d", &p);--p;printf("%d %d\n", ccnt[c[p]] - 1, bfs(p));}}}