結果

問題 No.30 たこやき工場
ユーザー ch1channn
提出日時 2023-09-24 08:33:13
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 106 ms / 5,000 ms
コード長 19,099 bytes
コンパイル時間 158 ms
コンパイル使用メモリ 82,140 KB
実行使用メモリ 79,464 KB
最終ジャッジ日時 2024-07-17 08:55:56
合計ジャッジ時間 2,324 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

from collections import *
from bisect import *
from math import *
from heapq import *
from itertools import *
def popcount(n):
    c=(n&0x5555555555555555)+((n>>1)&0x5555555555555555)
    c=(c&0x3333333333333333)+((c>>2)&0x3333333333333333)
    c=(c&0x0f0f0f0f0f0f0f0f)+((c>>4)&0x0f0f0f0f0f0f0f0f)
    c=(c&0x00ff00ff00ff00ff)+((c>>8)&0x00ff00ff00ff00ff)
    c=(c&0x0000ffff0000ffff)+((c>>16)&0x0000ffff0000ffff)
    c=(c&0x00000000ffffffff)+((c>>32)&0x00000000ffffffff)
    return c
"""
mod = 10**9+7
M= (10**5)*3+1 
fac= [1]*M
ninv= [1]*M
finv= [1]*M
for i in range(2,M):
  fac[i] = fac[i-1]*i%mod
  ninv[i] = (-(mod//i)*ninv[mod%i])%mod
  finv[i] = finv[i-1]*ninv[i]%mod
  
def binom(n,k):
  if n<0 or k<0:
    return 0
  if k>n:
    return 0
  return (fac[n]*finv[k]%mod)*finv[n-k]%mod
def nHk(n, k):
    return binom(n + k - 1, k)
"""
def nCk(n, k):
    k = min(k, n - k)
    ret = 1
    for i in range(n, n - k, -1): ret *= i
    for i in range(2, k + 1): ret //= i
    return ret
def nHk(n, k):
    return nCk(n + k - 1, k)
def nC2(x):
    return x*(x-1)//2
def is_prime(n):
    if n == 1: return False
    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.group = n
 
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
 
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
 
        if x == y:
            return
        self.group -= 1
        if self.parents[x] > self.parents[y]:
            x, y = y, x
 
        self.parents[x] += self.parents[y]
        self.parents[y] = x
 
    def size(self, x):
        return -self.parents[self.find(x)]
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
 
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
 
    def group_count(self):
        return self.group
 
    def all_group_members(self):
        dic = {r:[] for r in self.roots()}
        for i in range(self.n):
            dic[self.find(i)].append(i)
        return dic
 
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
class SOE:
  def __init__(self,m):
    self.sieve=[-1]*(m+1)
    self.prime=[]
    for i in range(2,m+1):
      if self.sieve[i]==-1:
        self.prime.append(i)
        self.sieve[i]=i
        j=2*i
        while j<=m:
          self.sieve[j]=i
          j+=i
  
  def primes(self):
    # get primes
    return self.prime
  
  def fact(self,n):
    # prime factorization
    d=[]
    while n!=1:
      p=self.sieve[n]
      d.append(p)
      while n%p==0:
        n//=p
    return d
  
def div(n):
    lower,upper = [],[]
    i = 1
    while i*i <= n:
        if n%i == 0:
            lower.append(i)
            if i!=n//i:
                upper.append(n//i)
        i += 1
    return lower+upper[::-1]
def factorize(x):
    yaku = []
    for i in range(2,int(x**0.5)+1):
        if x%i == 0:
            while x%i == 0:
                x //= i
                yaku.append(i)
    if x != 1:
        yaku.append(x)
    return yaku
#[2,3]この形
        
def fact(n):
  res=n
  a=[]
  i=2
  while i*i<=res:
    if res%i==0:
      cnt=0
      while res%i==0:
        cnt+=1
        res//=i
      a.append((i,cnt))
    i+=1
  if res!=1:
    a.append((res,1))
  return a
"""
[(2, 1), (3, 1)]この形
"""     
def nc2(x):
    return (x*(x-1)//2)
    
import random
class RollingHash:    
    mask30 = (1 << 30) - 1
    mask31 = (1 << 31) - 1
    MOD = (1 << 61) - 1
    Base = None
    pw = [1]
    
    def __init__(self, S):
        if RollingHash.Base is None:
            RollingHash.Base = random.randrange(129, 1 << 30)
        for i in range(len(RollingHash.pw), len(S) + 1):
            RollingHash.pw.append(RollingHash.CalcMod(RollingHash.Mul(RollingHash.pw[i - 1], self.__class__.Base)))
        
        self.hash = [0] * (len(S) + 1)
        for i, s in enumerate(S, 1):
            self.hash[i] = RollingHash.CalcMod(RollingHash.Mul(self.hash[i - 1], RollingHash.Base) + ord(s))
 
    def get(self, l, r):
        return RollingHash.CalcMod(self.hash[r] - RollingHash.Mul(self.hash[l], RollingHash.pw[r - l]))
 
    def Mul(l, r):
        lu = l >> 31
        ld = l & RollingHash.mask31
        ru = r >> 31
        rd = r & RollingHash.mask31
        middlebit = ld * ru + lu * rd
        return ((lu * ru) << 1) + ld * rd + \
            ((middlebit & RollingHash.mask30) << 31) + (middlebit >> 30)
 
    def CalcMod(val):
        if val < 0:
            val %= RollingHash.MOD
        val = (val & RollingHash.MOD) + (val >> 61)
        if val > RollingHash.MOD:
            val -= RollingHash.MOD
        return val
        
# https://github.com/tatyam-prime/SortedSet/blob/main/SortedMultiset.py
import math
from bisect import bisect_left, bisect_right, insort
from typing import Generic, Iterable, Iterator, TypeVar, Optional, List
T = TypeVar('T')
class SortedMultiset(Generic[T]):
    BUCKET_RATIO = 50
    REBUILD_RATIO = 170
    def _build(self, a=None) -> None:
        "Evenly divide `a` into buckets."
        if a is None: a = list(self)
        size = self.size = len(a)
        bucket_size = int(math.ceil(math.sqrt(size / self.BUCKET_RATIO)))
        self.a = [a[size * i // bucket_size : size * (i + 1) // bucket_size] for i in range(bucket_size)]
    
    def __init__(self, a: Iterable[T] = []) -> None:
        "Make a new SortedMultiset from iterable. / O(N) if sorted / O(N log N)"
        a = list(a)
        if not all(a[i] <= a[i + 1] for i in range(len(a) - 1)):
            a = sorted(a)
        self._build(a)
    def __iter__(self) -> Iterator[T]:
        for i in self.a:
            for j in i: yield j
    def __reversed__(self) -> Iterator[T]:
        for i in reversed(self.a):
            for j in reversed(i): yield j
    
    def __len__(self) -> int:
        return self.size
    
    def __repr__(self) -> str:
        return "SortedMultiset" + str(self.a)
    
    def __str__(self) -> str:
        s = str(list(self))
        return "{" + s[1 : len(s) - 1] + "}"
    def _find_bucket(self, x: T) -> List[T]:
        "Find the bucket which should contain x. self must not be empty."
        for a in self.a:
            if x <= a[-1]: return a
        return a
    def __contains__(self, x: T) -> bool:
        if self.size == 0: return False
        a = self._find_bucket(x)
        i = bisect_left(a, x)
        return i != len(a) and a[i] == x
    def count(self, x: T) -> int:
        "Count the number of x."
        return self.index_right(x) - self.index(x)
    def add(self, x: T) -> None:
        "Add an element. / O(√N)"
        if self.size == 0:
            self.a = [[x]]
            self.size = 1
            return
        a = self._find_bucket(x)
        insort(a, x)
        self.size += 1
        if len(a) > len(self.a) * self.REBUILD_RATIO:
            self._build()
    def discard(self, x: T) -> bool:
        "Remove an element and return True if removed. / O(√N)"
        if self.size == 0: return False
        a = self._find_bucket(x)
        i = bisect_left(a, x)
        if i == len(a) or a[i] != x: return False
        a.pop(i)
        self.size -= 1
        if len(a) == 0: self._build()
        return True
    def lt(self, x: T) -> Optional[T]:
        "Find the largest element < x, or None if it doesn't exist."
        for a in reversed(self.a):
            if a[0] < x:
                return a[bisect_left(a, x) - 1]
    def le(self, x: T) -> Optional[T]:
        "Find the largest element <= x, or None if it doesn't exist."
        for a in reversed(self.a):
            if a[0] <= x:
                return a[bisect_right(a, x) - 1]
    def gt(self, x: T) -> Optional[T]:
        "Find the smallest element > x, or None if it doesn't exist."
        for a in self.a:
            if a[-1] > x:
                return a[bisect_right(a, x)]
    def ge(self, x: T) -> Optional[T]:
        "Find the smallest element >= x, or None if it doesn't exist."
        for a in self.a:
            if a[-1] >= x:
                return a[bisect_left(a, x)]
    
    def __getitem__(self, x: int) -> T:
        "Return the x-th element, or IndexError if it doesn't exist."
        if x < 0: x += self.size
        if x < 0: raise IndexError
        for a in self.a:
            if x < len(a): return a[x]
            x -= len(a)
        raise IndexError
    def index(self, x: T) -> int:
        "Count the number of elements < x."
        ans = 0
        for a in self.a:
            if a[-1] >= x:
                return ans + bisect_left(a, x)
            ans += len(a)
        return ans
    def index_right(self, x: T) -> int:
        "Count the number of elements <= x."
        ans = 0
        for a in self.a:
            if a[-1] > x:
                return ans + bisect_right(a, x)
            ans += len(a)
        return ans
oo = 1<<60
ans = 0
cnt = 0
res = oo
def dijkstra(n, s, G):
    hq = [(0, s)]
    cost = [float('inf')] * n
    cost[s] = 0
    
    while hq:
        c,v = heappop(hq)
        if c > cost[v]:
            continue
        for nv,d in G[v]:
            tmp = d + cost[v]
            if tmp < cost[nv]:
                cost[nv] = tmp
                heappush(hq, (tmp,nv))
    return cost
class Topological_Sort:
    def __init__(self, N: int):
        """ N 頂点からなる空グラフを用意する.
 
        N: int
        """
        self.N=N
        self.arc=[[] for _ in  range(N)]
        self.rev=[[] for _ in range(N)]
 
    def add_arc(self, source: int, target: int):
        """ 有向辺 source → taeget を追加する.
 
        """
        self.arc[source].append(target)
        self.rev[target].append(source)
 
    def sort(self):
        """ トポロジカルソートを求める.
 
        [Ouput]
        存在する → トポロジカルソート
        存在しない → None
        """
 
        in_deg=[len(self.rev[x]) for x in range(self.N)]
        Q=[x for x in range(self.N) if in_deg[x]==0]
 
        S=[]
        while Q:
            u=Q.pop()
            S.append(u)
 
            for v in self.arc[u]:
                in_deg[v]-=1
                if in_deg[v]==0:
                    Q.append(v)
 
        return S if len(S)==self.N else None
 
    def is_DAG(self):
        """ DAG かどうかを判定する.
        """
        return self.sort()!=None
"""
class LowestCommonAncestor:
    def __init__(self,n):
        self._n=n;n=0
        while 2**(n/10)<self._n:n+=1
        self._logn=int(n/10+2)  #mathモジュールなしで構築
        self._depth=    [ 0 for _ in [0]*self._n]
        self._distance= [ 0 for _ in [0]*self._n]
        self._ancestor=[[-1 for _ in [0]*self._n] for k in [0]*self._logn]
        self._edge=     [[] for _ in [0]*self._n]
    def add_edge(self,u,v,w=1):  #頂点u,v間に重みwの辺を追加する
        self._edge[u].append((v,w))
        self._edge[v].append((u,w))
    def build(self,root=0):  #rootを指定し、その他の頂点に祖先情報を書き込む
        stack=[root]
        while stack:
            now=stack.pop()
            for nxt,w in self._edge[now]:
                if self._ancestor[0][nxt]!=now and self._ancestor[0][now]!=nxt:
                    self._ancestor[0][nxt]=now
                    self._depth[nxt]=   self._depth[now]   +1
                    self._distance[nxt]=self._distance[now]+w
                    stack.append(nxt)
        for k in range(1,self._logn):
            for i in range(self._n):
                if self._ancestor[k-1][i]==-1:
                     self._ancestor[k][i]=-1
                else:self._ancestor[k][i]=self._ancestor[k-1][self._ancestor[k-1][i]]
    def LCA(self,u,v):
        if self._depth[u]>self._depth[v]:u,v=v,u  #uが浅く、vが深い状態に
        for k in range(self._logn-1,-1,-1):  #vとuを同じ深度に
            if ((self._depth[v]-self._depth[u])>>k)&1:v=self._ancestor[k][v]
        if u==v:return u
        for k in range(self._logn-1,-1,-1):  #ギリギリ一致する直前まで祖先を辿る
            if self._ancestor[k][u]!=self._ancestor[k][v]:
                u,v=self._ancestor[k][u],self._ancestor[k][v]
        return self._ancestor[0][u]
    def distance(self,u,v):
        return self._distance[u]+self._distance[u]-2*self._distance[self.LCA(u,v)]
"""
import math
class LCA:
  def __init__(self,n):
    self._n=n
    self._logn=int(math.log2(self._n)+2)
    self._depth=[0]*self._n
    self._distance=[0]*self._n
    self._ancestor=[[-1]*self._n for k in range(self._logn)]
    self._edges=[[] for i in range(self._n)]
    
  def add_edge(self,u,v,w=1):
    self._edges[u].append((v,w))
    self._edges[v].append((u,w))
    
  def build(self,root=0):
    stack=[root]
    while len(stack):
      cur = stack.pop()
      for nxt,w in self._edges[cur]:
        if self._ancestor[0][nxt]!=cur and self._ancestor[0][cur]!=nxt:
          self._ancestor[0][nxt]=cur
          self._depth[nxt]=self._depth[cur]+1
          self._distance[nxt]=self._distance[cur]+w
          stack.append(nxt)
    
    for k in range(1,self._logn):
      for i in range(self._n):
        if self._ancestor[k-1][i]==-1:
          self._ancestor[k][i]=-1
        else:
          self._ancestor[k][i]=self._ancestor[k-1][self._ancestor[k-1][i]]
        
  def lca(self,u,v):
    if self._depth[u]>self._depth[v]:
      u,v=v,u
    
    for k in range(self._logn-1,-1,-1):
      if ((self._depth[v]-self._depth[u])>>k)&1:
        v=self._ancestor[k][v]
      
    if u==v:
      return u
    
    for k in range(self._logn-1,-1,-1):
      if self._ancestor[k][u]!=self._ancestor[k][v]:
        u=self._ancestor[k][u]
        v=self._ancestor[k][v]
    return self._ancestor[0][u]
  
  def distance(self,u,v):
    return self._distance[u]+self._distance[v]-2*self._distance[self.lca(u,v)]
  
class BIT_SortedSet:
    def __init__(self, A, compress=True, sort_flag=False):
        self.compress = compress
        self.N = len(A)
        self.log = 0
        while self.N >= 1 << (self.log + 1):
            self.log += 1
        if compress:
            if sort_flag:
                self.A = A
            else:
                self.A = sorted(A)
            self.index_dic = {}
            for i in range(len(A)):
                self.index_dic[self.A[i]] = i
        else:
            self.A = A
        self.BIT = [0] * (self.N + 5)
        self.size = 0
        self.cnt = [0] * self.N
    def BIT_add(self, i, x):
        idx = i + 1
        while idx < self.N + 1:
            self.BIT[idx] += x
            idx += idx & (-idx)
    def BIT_query(self, i):
        res = 0
        idx = i + 1
        while idx:
            res += self.BIT[idx]
            idx -= idx & (-idx)
        return res
    def BIT_lower_left(self, w):
        if w <= 0 or w > self.size:
            return None
        x = 0
        k = 1 << self.log
        while k > 0:
            if x + k < self.N and self.BIT[x + k] < w:
                w -= self.BIT[x + k]
                x += k
            k //= 2
        return x
    def __contains__(self, x):
        if self.compress:
            x = self.index_dic[x]
        return self.cnt[x] >= 1
    def __len__(self):
        return self.size
    def add(self, x):
        if self.compress:
            x = self.index_dic[x]
        if self.cnt[x] == 1:
            return False
        self.BIT_add(x, 1)
        self.size += 1
        self.cnt[x] += 1
        return True
    def discard(self, x):
        if self.compress:
            x = self.index_dic[x]
        if self.cnt[x] > 0:
            self.BIT_add(x, -1)
            self.size -= 1
            self.cnt[x] -= 1
            return True
        return False
    def find_kth_val(self, k):
        res = self.BIT_lower_left(k + 1)
        if res == None:
            return None
        if self.compress:
            res = self.A[res]
        return res
    def __getitem__(self, x):
        if x < 0:
            x += self.size
        if x < 0 or x >= self.size:
            raise IndexError
        return self.find_kth_val(x)
    def index_right(self, x):
        if x < self.A[0]:
            return 0
        if self.compress:
            y = bisect.bisect_right(self.A, x) - 1
        else:
            y = min(x, self.N - 1)
        return self.BIT_query(y)
    def index(self, x):
        if x <= self.A[0]:
            return 0
        if self.compress:
            y = bisect.bisect_right(self.A, x) - 1
        else:
            y = x
        if y >= self.N:
            y = self.N - 1
        elif self.A[y] == x:
            y -= 1
        return self.BIT_query(y)
    def gt(self, x):
        return self.find_kth_val(self.index_right(x))
    def ge(self, x):
        return self.find_kth_val(self.index(x))
    def lt(self, x):
        return self.find_kth_val(self.index(x) - 1)
    def le(self, x):
        return self.find_kth_val(self.index_right(x) - 1)
    def __str__(self):
        return (
            "{"
            + ", ".join(map(str, [self.find_kth_val(i) for i in range(self.size)]))
            + "}"
        )
def find_cycle(n,edge):
  seen=[0]*n
  finished=[0]*n
  stc=[]
  for i in range(n):
    if seen[i]:
      continue
    todo=[(1,i,-1),(0,i,-1)]
    seen[i]=True
    while todo:
      t,v,edge_id=todo.pop()
      if t==0:
        if finished[v]:
          continue
        seen[v]=1
        stc.append((v,edge_id))
        for u,id in edge[v]:
          if finished[v]:
            continue
          
          if seen[u] and finished[u]==0:
            cyc=[id]
            while stc:
              v,id=stc.pop()
              if v==u:
                break
              cyc.append(id)
            return cyc[::-1]
          
          elif seen[u]==0:
            todo.append((1,u,id))
            todo.append((0,u,id))
      
      else:
        if finished[v]:
          continue
        stc.pop()
        finished[v]=1
  
  return []
import sys
if sys.platform =='ios':
    import clipboard
    a=clipboard.get()
    a = a.split('\n')
    text = '\n'.join(a)
    with open('input_file.txt','w') as f:
        f.write(text)
    sys.stdin = open('input_file.txt')
sys.setrecursionlimit(410000000)
stdin = sys.stdin 
def ni():return int(ns())
def na():return list(map(int, stdin.readline().split()))
def ns():return stdin.readline().strip()
def nm():return map(int,input().split())
def na_1():return list(map(lambda x:int(x)*(-1), stdin.readline().split()))
def na_2():return list(map(lambda x:int(x)-1, stdin.readline().split()))
rnage=range
rnge=range
rage = range
N = ni()
M = ni()
ind = [0]*N
G = [[]for i in range(N)]
for i in range(M):
    p,x,q = nm()
    G[q-1].append((p-1,x))
    ind[p-1] += 1
todo = []
for i in range(N):
    if ind[i] == 0:
        todo.append(i)
dp = [0]*N
dp[N-1] = 1
ans = [0]*N
while todo:
    v = todo.pop()
    if len(G[v]) == 0:
        ans[v] = dp[v]
    for nv,c in G[v]:
        dp[nv] += dp[v]*c
        ind[nv] -= 1
        if ind[nv] == 0:
            todo.append(nv)
            
print(*ans[:-1],sep="\n")
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0