Submission #16494611


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())))

mat.todense()

Submission Info

Submission Time
Task E - Page Rank
User maspy
Language Python (3.8.2)
Score 100
Code Size 716 Byte
Status AC
Exec Time 274 ms
Memory 89908 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 197 ms 43868 KB
10_sample_02.txt AC 196 ms 44080 KB
20-random_small-00.txt AC 200 ms 44428 KB
20-random_small-01.txt AC 203 ms 44476 KB
20-random_small-02.txt AC 201 ms 43932 KB
20-random_small-03.txt AC 195 ms 44264 KB
20-random_small-04.txt AC 196 ms 44212 KB
20-random_small-05.txt AC 199 ms 43896 KB
20-random_small-06.txt AC 196 ms 44172 KB
20-random_small-07.txt AC 195 ms 44856 KB
20-random_small-08.txt AC 198 ms 44488 KB
20-random_small-09.txt AC 200 ms 44200 KB
30-random_large-00.txt AC 201 ms 44912 KB
30-random_large-01.txt AC 207 ms 45720 KB
30-random_large-02.txt AC 251 ms 83740 KB
30-random_large-03.txt AC 242 ms 71464 KB
30-random_large-04.txt AC 207 ms 57720 KB
30-random_large-05.txt AC 221 ms 60436 KB
30-random_large-06.txt AC 208 ms 51860 KB
30-random_large-07.txt AC 222 ms 58280 KB
30-random_large-08.txt AC 264 ms 81120 KB
30-random_large-09.txt AC 268 ms 86100 KB
40-random_max-00.txt AC 269 ms 89908 KB
40-random_max-01.txt AC 267 ms 89644 KB
40-random_max-02.txt AC 274 ms 89716 KB