Submission #8433304
Source Code Expand
import os import sys import numpy as np if os.getenv("LOCAL"): sys.stdin = open("_in.txt", "r") sys.setrecursionlimit(10 ** 9) INF = float("inf") IINF = 10 ** 18 MOD = 10 ** 9 + 7 # MOD = 998244353 N, M = list(map(int, sys.stdin.readline().split())) AB = [list(map(int, sys.stdin.readline().split())) for _ in range(M)] graph = [set() for _ in range(N)] for a, b in AB: a -= 1 b -= 1 graph[a].add(b) # 方程式にして解く # 反復法 ans = np.zeros((N, 20)) ans[:, -1] = 0.1 mat = np.zeros((20, N)) mat[-1] = 1 for i in range(N): for j in range(-9, 10): if not 0 <= i + j < N: continue if i in graph[i + j]: mat[j + 9, i] = 0.9 / len(graph[i + j]) mat = mat.T for _ in range(1000): # ans と mat.T の積の対角成分だけ取り出す # https://stackoverflow.com/a/14759273 next_ans = (ans * mat).sum(-1) ans[:] = 0 ans[:, 9] = next_ans for i in range(1, min(10, N)): ans[i:, 9 - i] = next_ans[:-i] ans[:-i, 9 + i] = next_ans[i:] ans[:, -1] = 0.1 print(*ans[:, 9], sep="\n")
Submission Info
Submission Time | |
---|---|
Task | E - Page Rank |
User | nohtaray |
Language | Python (3.4.3) |
Score | 100 |
Code Size | 1144 Byte |
Status | AC |
Exec Time | 1733 ms |
Memory | 21972 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 100 / 100 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | 10_sample_01.txt, 10_sample_02.txt, 20-random_small-00.txt, 20-random_small-01.txt, 20-random_small-02.txt, 20-random_small-03.txt, 20-random_small-04.txt, 20-random_small-05.txt, 20-random_small-06.txt, 20-random_small-07.txt, 20-random_small-08.txt, 20-random_small-09.txt, 30-random_large-00.txt, 30-random_large-01.txt, 30-random_large-02.txt, 30-random_large-03.txt, 30-random_large-04.txt, 30-random_large-05.txt, 30-random_large-06.txt, 30-random_large-07.txt, 30-random_large-08.txt, 30-random_large-09.txt, 40-random_max-00.txt, 40-random_max-01.txt, 40-random_max-02.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
10_sample_01.txt | AC | 188 ms | 12524 KB |
10_sample_02.txt | AC | 187 ms | 12396 KB |
20-random_small-00.txt | AC | 244 ms | 12552 KB |
20-random_small-01.txt | AC | 240 ms | 12552 KB |
20-random_small-02.txt | AC | 236 ms | 12396 KB |
20-random_small-03.txt | AC | 247 ms | 12636 KB |
20-random_small-04.txt | AC | 234 ms | 12440 KB |
20-random_small-05.txt | AC | 238 ms | 12552 KB |
20-random_small-06.txt | AC | 236 ms | 12440 KB |
20-random_small-07.txt | AC | 245 ms | 12680 KB |
20-random_small-08.txt | AC | 244 ms | 12636 KB |
20-random_small-09.txt | AC | 238 ms | 12396 KB |
30-random_large-00.txt | AC | 280 ms | 12808 KB |
30-random_large-01.txt | AC | 277 ms | 13064 KB |
30-random_large-02.txt | AC | 1554 ms | 19420 KB |
30-random_large-03.txt | AC | 1140 ms | 17740 KB |
30-random_large-04.txt | AC | 666 ms | 14764 KB |
30-random_large-05.txt | AC | 748 ms | 16056 KB |
30-random_large-06.txt | AC | 443 ms | 14284 KB |
30-random_large-07.txt | AC | 678 ms | 15736 KB |
30-random_large-08.txt | AC | 1425 ms | 19808 KB |
30-random_large-09.txt | AC | 1613 ms | 20696 KB |
40-random_max-00.txt | AC | 1733 ms | 21904 KB |
40-random_max-01.txt | AC | 1720 ms | 21944 KB |
40-random_max-02.txt | AC | 1712 ms | 21972 KB |