Submission #8178689


Source Code Expand

Copy
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <math.h>
//const long long mod = 1000000007;
//const long long mod = 998244353;

int main() {
	int N, M;
	scanf("%d %d", &N, &M);
	std::vector<int>* p = new std::vector<int>[N];
	for (int i = 0; i < M; i++) {
		int s, t;
		scanf("%d %d", &s, &t);
		p[s - 1].push_back(t - 1);
	}
	double*P = new double[N];
	for (int i = 0; i < N; i++)P[i] = 0;
	P[0] = 1;
	for (int i = 0; i < N - 1; i++) {
		for (int j = 0; j < p[i].size(); j++) {
			P[p[i][j]] += P[i] / p[i].size();
		}
	}
	double*E = new double[N];
	E[N - 1] = 0;
	double best = N;
	for (int i = N - 2; i >= 0; i--) {
		double sum = 0;
		for (int j = 0; j < p[i].size(); j++) {
			sum += E[p[i][j]];
		}
		E[i] = sum / p[i].size() + 1;
		if (p[i].size() == 1)continue;
		for (int j = 0; j < p[i].size(); j++) {
			double d = (sum - E[p[i][j]]) / (p[i].size() - 1) + 1 - E[i];
			if (best > d*P[i])best = d * P[i];
		}
	}
	if (best < 0) {
		printf("%f", E[0] + best);
	}
	else {
		printf("%f", E[0]);
	}
	return 0;
}

Submission Info

Submission Time
Task F - Fork in the Road
User kitsan
Language C++14 (GCC 5.4.1)
Score 600
Code Size 1119 Byte
Status AC
Exec Time 30 ms
Memory 1408 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:12:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &M);
                        ^
./Main.cpp:16:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &s, &t);
                         ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 65
Set Name Test Cases
Sample 00-sample-00, 00-sample-01, 00-sample-02
All 00-sample-00, 00-sample-01, 00-sample-02, 01-handmade-03, 01-handmade-04, 01-handmade-05, 01-handmade-06, 01-handmade-07, 01-handmade-08, 01-handmade-09, 02-small-10, 02-small-11, 02-small-12, 02-small-13, 02-small-14, 02-small-15, 02-small-16, 02-small-17, 02-small-18, 02-small-19, 02-small-20, 02-small-21, 02-small-22, 02-small-23, 02-small-24, 03-medium-25, 03-medium-26, 03-medium-27, 03-medium-28, 03-medium-29, 03-medium-30, 03-medium-31, 03-medium-32, 03-medium-33, 03-medium-34, 03-medium-35, 03-medium-36, 03-medium-37, 03-medium-38, 03-medium-39, 03-medium-40, 03-medium-41, 03-medium-42, 03-medium-43, 03-medium-44, 04-large-45, 04-large-46, 04-large-47, 04-large-48, 04-large-49, 04-large-50, 04-large-51, 04-large-52, 04-large-53, 04-large-54, 04-large-55, 04-large-56, 04-large-57, 04-large-58, 04-large-59, 04-large-60, 04-large-61, 04-large-62, 04-large-63, 04-large-64
Case Name Status Exec Time Memory
00-sample-00 AC 1 ms 256 KB
00-sample-01 AC 1 ms 256 KB
00-sample-02 AC 1 ms 256 KB
01-handmade-03 AC 30 ms 1408 KB
01-handmade-04 AC 30 ms 1408 KB
01-handmade-05 AC 1 ms 256 KB
01-handmade-06 AC 29 ms 1408 KB
01-handmade-07 AC 1 ms 256 KB
01-handmade-08 AC 9 ms 640 KB
01-handmade-09 AC 1 ms 256 KB
02-small-10 AC 1 ms 256 KB
02-small-11 AC 1 ms 256 KB
02-small-12 AC 1 ms 256 KB
02-small-13 AC 1 ms 256 KB
02-small-14 AC 1 ms 256 KB
02-small-15 AC 1 ms 256 KB
02-small-16 AC 1 ms 256 KB
02-small-17 AC 1 ms 256 KB
02-small-18 AC 1 ms 256 KB
02-small-19 AC 1 ms 256 KB
02-small-20 AC 1 ms 256 KB
02-small-21 AC 1 ms 256 KB
02-small-22 AC 1 ms 256 KB
02-small-23 AC 1 ms 256 KB
02-small-24 AC 1 ms 256 KB
03-medium-25 AC 1 ms 256 KB
03-medium-26 AC 1 ms 256 KB
03-medium-27 AC 1 ms 256 KB
03-medium-28 AC 1 ms 256 KB
03-medium-29 AC 1 ms 256 KB
03-medium-30 AC 1 ms 256 KB
03-medium-31 AC 1 ms 256 KB
03-medium-32 AC 1 ms 256 KB
03-medium-33 AC 1 ms 256 KB
03-medium-34 AC 1 ms 256 KB
03-medium-35 AC 1 ms 256 KB
03-medium-36 AC 1 ms 256 KB
03-medium-37 AC 1 ms 256 KB
03-medium-38 AC 1 ms 256 KB
03-medium-39 AC 1 ms 256 KB
03-medium-40 AC 1 ms 256 KB
03-medium-41 AC 1 ms 256 KB
03-medium-42 AC 1 ms 256 KB
03-medium-43 AC 1 ms 256 KB
03-medium-44 AC 1 ms 256 KB
04-large-45 AC 1 ms 256 KB
04-large-46 AC 2 ms 384 KB
04-large-47 AC 5 ms 384 KB
04-large-48 AC 9 ms 512 KB
04-large-49 AC 13 ms 768 KB
04-large-50 AC 1 ms 256 KB
04-large-51 AC 2 ms 256 KB
04-large-52 AC 6 ms 512 KB
04-large-53 AC 9 ms 512 KB
04-large-54 AC 16 ms 768 KB
04-large-55 AC 1 ms 256 KB
04-large-56 AC 2 ms 384 KB
04-large-57 AC 6 ms 512 KB
04-large-58 AC 9 ms 512 KB
04-large-59 AC 13 ms 640 KB
04-large-60 AC 1 ms 256 KB
04-large-61 AC 2 ms 256 KB
04-large-62 AC 6 ms 512 KB
04-large-63 AC 10 ms 640 KB
04-large-64 AC 16 ms 768 KB