Submission #1404051
Source Code Expand
#include <stdio.h> #include <vector> #include <queue> using namespace std; vector<int> G[100100]; int N, M, D[2][100100], C[2][100100]; int main() { int s, t; scanf("%d %d %d %d", &N, &M, &s, &t); for (int i=0;i<M;i++){ int x, y; scanf("%d %d", &x, &y); G[x].push_back(y); G[y].push_back(x); } for (int i=1;i<=N;i++) D[0][i] = D[1][i] = -1; for (int k=0;k<2;k++){ queue<int> Q; if (k == 0) Q.push(s), D[k][s] = 0; else Q.push(t), D[k][t] = 0; while (!Q.empty()){ int x = Q.front(); Q.pop(); for (auto &y : G[x]) if (D[k][y] == -1){ Q.push(y); D[k][y] = D[k][x] + 1; } } } int d = D[0][t]; long long ans = 0; for (int i=1;i<=N;i++){ if (D[0][i] != -1) C[0][D[0][i]]++; if (D[1][i] != -1) C[1][D[1][i]]++; } for (int i=0;i<=d-2;i++) ans += (long long)C[0][i] * C[1][d-2-i]; printf("%lld\n", ans); return 0; }
Submission Info
Submission Time | |
---|---|
Task | B - Minus One |
User | august14 |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 903 Byte |
Status | AC |
Exec Time | 147 ms |
Memory | 7544 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:13:38: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d %d %d %d", &N, &M, &s, &t); ^ ./Main.cpp:15:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] int x, y; scanf("%d %d", &x, &y); ^
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 100 / 100 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | 00-sample1.txt, 00-sample2.txt, 00-sample4.txt, 50-random10.txt, 50-random11.txt, 50-random12.txt, 50-random13.txt, 50-random14.txt, 50-random15.txt, 50-random16.txt, 50-random17.txt, 50-random18.txt, 50-random19.txt, 50-random20.txt, 50-random21.txt, 50-random22.txt, 50-random23.txt, 50-random24.txt, 50-random25.txt, 50-random26.txt, 50-random27.txt, 50-random28.txt, 50-random29.txt, 50-random30.txt, 50-random31.txt, 50-random32.txt, 50-random33.txt, 50-random34.txt, 50-random35.txt, 50-random36.txt, 50-random37.txt, 50-random38.txt, 50-random39.txt, 50-random40.txt, 50-random41.txt, 50-random42.txt, 50-random43.txt, 50-random44.txt, 50-random45.txt, 50-random46.txt, 50-random47.txt, 50-random48.txt, 50-random49.txt, 50-random50.txt, 50-random51.txt, 50-random52.txt, 50-random53.txt, 50-random54.txt, 50-random55.txt, 50-random56.txt, 50-random57.txt, 50-random58.txt, 50-random59.txt, 50-random60.txt, 50-random61.txt, 50-random62.txt, 50-random63.txt, 50-random64.txt, 50-random65.txt, 50-random66.txt, 50-random67.txt, 50-random68.txt, 50-random69.txt, intoverflow00.txt, intoverflow01.txt, intoverflow02.txt, intoverflow03.txt, intoverflow04.txt, intoverflow05.txt, intoverflow06.txt, intoverflow07.txt, intoverflow08.txt, intoverflow09.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00-sample1.txt | AC | 2 ms | 2560 KB |
00-sample2.txt | AC | 2 ms | 2560 KB |
00-sample4.txt | AC | 2 ms | 2560 KB |
50-random10.txt | AC | 2 ms | 2560 KB |
50-random11.txt | AC | 2 ms | 2560 KB |
50-random12.txt | AC | 2 ms | 2560 KB |
50-random13.txt | AC | 2 ms | 2560 KB |
50-random14.txt | AC | 2 ms | 2560 KB |
50-random15.txt | AC | 2 ms | 2560 KB |
50-random16.txt | AC | 2 ms | 2560 KB |
50-random17.txt | AC | 2 ms | 2560 KB |
50-random18.txt | AC | 2 ms | 2560 KB |
50-random19.txt | AC | 2 ms | 2560 KB |
50-random20.txt | AC | 2 ms | 2560 KB |
50-random21.txt | AC | 2 ms | 2560 KB |
50-random22.txt | AC | 2 ms | 2560 KB |
50-random23.txt | AC | 2 ms | 2560 KB |
50-random24.txt | AC | 2 ms | 2560 KB |
50-random25.txt | AC | 2 ms | 2560 KB |
50-random26.txt | AC | 2 ms | 2560 KB |
50-random27.txt | AC | 2 ms | 2560 KB |
50-random28.txt | AC | 2 ms | 2560 KB |
50-random29.txt | AC | 2 ms | 2560 KB |
50-random30.txt | AC | 2 ms | 2560 KB |
50-random31.txt | AC | 2 ms | 2560 KB |
50-random32.txt | AC | 2 ms | 2560 KB |
50-random33.txt | AC | 2 ms | 2560 KB |
50-random34.txt | AC | 2 ms | 2560 KB |
50-random35.txt | AC | 2 ms | 2560 KB |
50-random36.txt | AC | 2 ms | 2560 KB |
50-random37.txt | AC | 2 ms | 2560 KB |
50-random38.txt | AC | 2 ms | 2560 KB |
50-random39.txt | AC | 2 ms | 2560 KB |
50-random40.txt | AC | 3 ms | 2688 KB |
50-random41.txt | AC | 2 ms | 2560 KB |
50-random42.txt | AC | 2 ms | 2688 KB |
50-random43.txt | AC | 2 ms | 2560 KB |
50-random44.txt | AC | 3 ms | 2560 KB |
50-random45.txt | AC | 2 ms | 2560 KB |
50-random46.txt | AC | 3 ms | 2688 KB |
50-random47.txt | AC | 3 ms | 2688 KB |
50-random48.txt | AC | 3 ms | 2688 KB |
50-random49.txt | AC | 3 ms | 2688 KB |
50-random50.txt | AC | 4 ms | 2816 KB |
50-random51.txt | AC | 8 ms | 3072 KB |
50-random52.txt | AC | 4 ms | 2688 KB |
50-random53.txt | AC | 7 ms | 2944 KB |
50-random54.txt | AC | 8 ms | 3072 KB |
50-random55.txt | AC | 8 ms | 3072 KB |
50-random56.txt | AC | 3 ms | 2688 KB |
50-random57.txt | AC | 5 ms | 2816 KB |
50-random58.txt | AC | 4 ms | 2816 KB |
50-random59.txt | AC | 4 ms | 2816 KB |
50-random60.txt | AC | 40 ms | 5376 KB |
50-random61.txt | AC | 38 ms | 5120 KB |
50-random62.txt | AC | 62 ms | 6512 KB |
50-random63.txt | AC | 39 ms | 5120 KB |
50-random64.txt | AC | 42 ms | 5504 KB |
50-random65.txt | AC | 16 ms | 3712 KB |
50-random66.txt | AC | 14 ms | 3968 KB |
50-random67.txt | AC | 6 ms | 3328 KB |
50-random68.txt | AC | 6 ms | 2944 KB |
50-random69.txt | AC | 4 ms | 3072 KB |
intoverflow00.txt | AC | 147 ms | 7544 KB |
intoverflow01.txt | AC | 61 ms | 7540 KB |
intoverflow02.txt | AC | 58 ms | 7536 KB |
intoverflow03.txt | AC | 60 ms | 7544 KB |
intoverflow04.txt | AC | 58 ms | 7540 KB |
intoverflow05.txt | AC | 61 ms | 7540 KB |
intoverflow06.txt | AC | 58 ms | 7540 KB |
intoverflow07.txt | AC | 60 ms | 7544 KB |
intoverflow08.txt | AC | 59 ms | 7544 KB |
intoverflow09.txt | AC | 62 ms | 7544 KB |