Problem p02702 (python)

Fixed submission:


from functools import *
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline




def acinput():
    return list(map(int, input().split(" ")))


def II():
    return int(input())

mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact



def serch(x, count):
    #print("top", x, count)
            

    for d in directions:
        nx = d+x
        #print(nx)
        if np.all(0 <= nx) and np.all(nx < (H, W)):
            if field[nx[0]][nx[1]] == "E":
                count += 1 
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)  
                continue
            if field[nx[0]][nx[1]] == "#":
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)    
                 
    return count

#S=list(map(int,list(input())[:-1]))[::-1]
S=list(map(int,list(input())[:-1]))
#print(S)

N=len(S)
smod=[0]*N
bef=0
b=1

for i in range(len(S)):
    l=N-i-1
    bef+=(S[l]*(b))%2019
    smod[l]=bef%2019
    #smod.append(bef%2019)
    b=(b*10)%2019
    
cnt=[0]*2020
for sm in smod:
    cnt[sm]+=1

cnt[0]+=1

res=0
for sc in cnt:
    res+=sc*(sc-1)/2
    
    
print(int(res))

#print(smod)

#print(cnt[:10])

Buggy submission (verdict: Runtime Error):

import numpy as np
from functools import *
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline


def acinput():
    return list(map(int, input().split(" ")))


def II():
    return int(input())


directions = np.array([[1, 0], [0, 1], [-1, 0], [0, -1]])
directions = list(map(np.array, directions))

mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact


def serch(x, count):
    # print("top", x, count)

    for d in directions:
        nx = d+x
        # print(nx)
        if np.all(0 <= nx) and np.all(nx < (H, W)):
            if field[nx[0]][nx[1]] == "E":
                count += 1
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)
                continue
            if field[nx[0]][nx[1]] == "#":
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)

    return count


class Node:
    def __init__(self):
        pass


class Edge:
    def __init__(self, edge, cost=1):
        self.node_from = edge[0]
        self.node_to = edge[1]
        self.cost = cost

    def add_node(self, node):
        self.nodes.append(node)


class myGraph:

    def __init__(self, V=False):
        self.adj = {}
        self.nodes = {}

        if V > 0:
            for v in range(0, V):
                self.nodes[v] = {}
                self.adj[v] = {}

    def add_edge(self, edge, cost):
        if len(edge) == 1:
            edge = list(edge)

        u, v = edge[0], edge[1]

        if u not in self.nodes:
            self.adj[u] = {}
            self.nodes[u] = {}

        if v not in self.nodes:
            self.adj[v] = {}
            self.nodes[v] = {}

        # add the edge
        self.adj[u][v] = cost
        self.adj[v][u] = cost

    def add_directed_edge(self, edge, cost):
        if len(edge) == 1:
            edge = list(edge)

        u, v = edge[0], edge[1]

        if u not in self.nodes:
            self.adj[u] = {}
            self.nodes[u] = {}

        if v not in self.nodes:
            self.adj[v] = {}
            self.nodes[v] = {}

        self.adj[u][v] = cost

    def get_edges_from(self, node):
        return [(self.adj[node][nn], node, nn) for nn in self.adj[node]]

    def WarshallFloyd(self):
        return 0

    def is_nibu(self):
        return False

    def makeEdgeobj(self):
        edges = []
        for sn in self.nodes:
            for e in self.get_edges_from(sn):
                edges.append(Edge([e[1], e[2]], e[0]))

        return edges

    def _add(self, edges, add_edges):
        for e in add_edges:
            hq.heappush(edges, e)
        return edges

    def bermn_ford(self, start, init=0):

        nodes = self.nodes
        dists = {}
        for n in nodes:
            dists[n] = float("inf")

        dists[start] = init
        edges = self.makeEdgeobj()

        for i in range(len(nodes)):
            update = False
            for k in range(len(edges)):
                e = edges[k]
                if dists[e.node_from] != float("inf") and dists[e.node_to] > dists[e.node_from]+e.cost:
                    dists[e.node_to] = dists[e.node_from]+e.cost
                    update = True

            if i == len(nodes)-1:
                return False

            if not update:
                break

        return dists
    
    def dijkstra(self, start, goal=None):
        import heapq
        '''
            get minimum cost
        '''

        N = len(self.nodes)          # グラフのノード数
        # dist = [float('inf') for i in range(N)] # 始点から各頂点までの最短距離を格納する
        
        dist = {k: float('inf') for k in self.nodes}
        # prev = [float('inf') for i in range(N)]

        dist[start] = 0
        # print(self.nodes)
        if N == 0:
            return dist
        visited = []

        koho = []
        heapq.heappush(koho, (0, start))

        # vtx=list(self.nodes)
        # vtx.remove(start)

        ginka=self.S
        while len(koho) != 0:
            d, mini = heapq.heappop(koho)
            if dist[mini] < d:
                continue
            
            adjs=self.dadj(mini)
            for k in range(len(adjs)):
                #cost = self.adj[mini][k]
                cost=self.dadj(mini,ginka)
                # and not(k in visited):
                if cost != float('inf') and dist[k] > dist[mini]+cost:
                    dist[k] = dist[mini]+cost
                    heapq.heappush(koho, (dist[k], k))
                    # prev[k]=mini

        return dist

    #def dadj(self,n):
    #    self.
        
    def show(self):
        import networkx as nx
        import matplotlib.pyplot as plt
        G=nx.Graph()

        for u in self.adj:
            for v in self.adj[u]:

                # G.add_edge(e.node_from,e.node_to,weight=e.cost)
                G.add_edge(u,v,weight=self.adj[u][v])
                # print(e.node_from,e.node_to,e.cost)

        pos=nx.spring_layout(G)
        # nx.draw_networkx_edges(G,pos=pos,edgelist=G.edges())
        edge_weight=dict([((u,v,),int(d['weight'])) for u,v,d in G.edges(data=True)])

        nx.draw_networkx_edge_labels(G,pos,edge_labels=edge_weight)
        # nx.draw_networkx_labels(G, pos)
        nx.draw_networkx_nodes(G,pos)
        nx.draw_networkx_edges(G,pos)
        nx.draw_networkx_labels(G,pos)
        # plt.axis('off')
        # nx.draw(G,with_labels=True)
        plt.show()

def search(x):
    global g,N,nodenum
    queue=[(x,1)]
    wnum=2
    nodenum=[-1]*N
    nodenum[x]=1
    visited=[0]*N
    while True:
        nqueue=[]
        for node,k in queue:
            for snode in g[node]:
                if nodenum[snode]<0:                    
                    nodenum[snode]=wnum
                    nqueue.append((snode,wnum))
                else:
                    if (not visited[snode]) and nodenum[snode]!=wnum:
                        return -1
            visited[node]=1

        queue=nqueue
        if len(queue)==0:
            return wnum-1
        wnum+=1
        


def acinput():
    s=input()
    if len(s)==0:
        return False

    return list(map(int,s.split(" ")))
    

if __name__=="__main__":
    # a=spaceinput()
    N,M,S=acinput()
    g=myGraph()
    g.S=S

    d=[]
    for i in range(M):
        tmp=acinput()
        d.append(tmp)
        g.add_edge((tmp[0],tmp[1]),1)

    cost=[]
    for i in range(N):
        cost.append(acinput())

    for i in range(N):
        self.nodes.append(i+1)
        
    res=g.dijkstra(1)
    print(res)
    '''
    mint=10*9
    for k in range(1,n+1):
        dd=g.dijkstra(k)
        v=max(dd.values())
        if mint>v:
            mint=v


    print(mint)
    '''

'''
1 2 7
2 3 8
1 4 5
2 4 9
2 5 7
3 5 5
4 5 15
4 6 6
5 6 8
5 7 9
6 7 11

'''