Submission #16494614


Source Code Expand

Copy
import sys
from scipy.sparse import csr_matrix
import scipy.sparse.linalg as sp

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, M = map(int, readline().split())
m = map(int, read().split())
G = [[] for _ in range(N)]
in_deg = [0] * N
for a, b in zip(m, m):
    a, b = b, a
    a -= 1
    b -= 1
    G[a].append(b)
    in_deg[b] += 1

A = []
for a in range(N):
    A.append((a, a, 1))
    for b in G[a]:
        v = -0.9 / in_deg[b]
        A.append((a, b, v))
rows, cols, vals = zip(*A)

mat = csr_matrix((vals, (rows, cols)), (N, N))
ans = sp.spsolve(mat, [0.1] * N)
print('\n'.join(map(str, ans.tolist())))

Submission Info

Submission Time
Task E - Page Rank
User maspy
Language Python (3.8.2)
Score 100
Code Size 701 Byte
Status AC
Exec Time 232 ms
Memory 52820 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 198 ms 43892 KB
10_sample_02.txt AC 192 ms 43476 KB
20-random_small-00.txt AC 195 ms 44184 KB
20-random_small-01.txt AC 197 ms 44024 KB
20-random_small-02.txt AC 195 ms 44348 KB
20-random_small-03.txt AC 197 ms 44408 KB
20-random_small-04.txt AC 195 ms 43928 KB
20-random_small-05.txt AC 194 ms 43540 KB
20-random_small-06.txt AC 194 ms 43872 KB
20-random_small-07.txt AC 189 ms 44176 KB
20-random_small-08.txt AC 193 ms 44328 KB
20-random_small-09.txt AC 197 ms 44092 KB
30-random_large-00.txt AC 194 ms 44384 KB
30-random_large-01.txt AC 206 ms 44424 KB
30-random_large-02.txt AC 224 ms 50488 KB
30-random_large-03.txt AC 203 ms 48456 KB
30-random_large-04.txt AC 206 ms 46680 KB
30-random_large-05.txt AC 213 ms 47432 KB
30-random_large-06.txt AC 202 ms 45616 KB
30-random_large-07.txt AC 202 ms 47272 KB
30-random_large-08.txt AC 219 ms 50604 KB
30-random_large-09.txt AC 225 ms 51496 KB
40-random_max-00.txt AC 229 ms 52764 KB
40-random_max-01.txt AC 232 ms 52820 KB
40-random_max-02.txt AC 229 ms 52524 KB