Contest Duration: - (local time) (100 minutes) Back to Home

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 2019-10-27 23:05:56+0900 F - Fork in the Road kitsan C++14 (GCC 5.4.1) 600 1119 Byte AC 30 ms 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