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