Submission #8175355


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::pair<int, int>* p = new std::pair<int, int>[M];
	for (int i = 0; i < M; i++) {
		int s, t;
		scanf("%d %d", &s, &t);
		p[i].first = s - 1;
		p[i].second = t - 1;
	}
	std::sort(p, p + M);
	double best = N;
	for (int skip = 0; skip <= M; skip++) {
		double*E = new double[N];
		E[N - 1] = 0;
		int s = M - 1;
		for (int i = N - 2; i >= 0; i--) {
			double sum = 0;
			int cnt = 0;
			for (; p[s].first == i; s--) {
				if (s == skip)continue;
				cnt++;
				sum += E[p[s].second];
			}
			E[i] = sum / cnt + 1;
		}
		if (E[0] < best)best = E[0];
	}
	printf("%f", best);
	return 0;
}

Submission Info

Submission Time
Task F - Fork in the Road
User kitsan
Language C++14 (GCC 5.4.1)
Score 0
Code Size 857 Byte
Status TLE
Exec Time 2115 ms
Memory 193280 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 0 / 600
Status
AC × 3
AC × 53
TLE × 12
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 TLE 2107 ms 55552 KB
01-handmade-04 TLE 2106 ms 55552 KB
01-handmade-05 AC 1 ms 256 KB
01-handmade-06 TLE 2106 ms 56576 KB
01-handmade-07 AC 6 ms 5888 KB
01-handmade-08 TLE 2115 ms 185472 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 2 ms 640 KB
03-medium-27 AC 2 ms 512 KB
03-medium-28 AC 2 ms 640 KB
03-medium-29 AC 8 ms 1920 KB
03-medium-30 AC 1 ms 256 KB
03-medium-31 AC 2 ms 512 KB
03-medium-32 AC 3 ms 896 KB
03-medium-33 AC 5 ms 1152 KB
03-medium-34 AC 6 ms 1664 KB
03-medium-35 AC 1 ms 512 KB
03-medium-36 AC 2 ms 640 KB
03-medium-37 AC 7 ms 1792 KB
03-medium-38 AC 3 ms 768 KB
03-medium-39 AC 2 ms 384 KB
03-medium-40 AC 1 ms 384 KB
03-medium-41 AC 2 ms 512 KB
03-medium-42 AC 6 ms 1536 KB
03-medium-43 AC 6 ms 1536 KB
03-medium-44 AC 4 ms 1280 KB
04-large-45 AC 9 ms 7424 KB
04-large-46 AC 74 ms 28800 KB
04-large-47 AC 769 ms 114176 KB
04-large-48 TLE 2115 ms 188416 KB
04-large-49 TLE 2111 ms 120320 KB
04-large-50 AC 9 ms 8064 KB
04-large-51 AC 66 ms 26624 KB
04-large-52 AC 866 ms 123776 KB
04-large-53 TLE 2114 ms 183424 KB
04-large-54 TLE 2109 ms 107392 KB
04-large-55 AC 9 ms 7552 KB
04-large-56 AC 76 ms 29696 KB
04-large-57 AC 794 ms 115328 KB
04-large-58 TLE 2114 ms 193280 KB
04-large-59 TLE 2110 ms 120704 KB
04-large-60 AC 10 ms 8448 KB
04-large-61 AC 73 ms 29056 KB
04-large-62 AC 843 ms 127104 KB
04-large-63 TLE 2114 ms 176512 KB
04-large-64 TLE 2109 ms 103552 KB