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
AC × 73
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