結果
問題 | No.2640 traO Stamps |
ユーザー |
![]() |
提出日時 | 2024-02-19 22:31:19 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 588 ms / 2,000 ms |
コード長 | 2,656 bytes |
コンパイル時間 | 187 ms |
コンパイル使用メモリ | 82,328 KB |
実行使用メモリ | 105,112 KB |
最終ジャッジ日時 | 2024-09-29 02:23:27 |
合計ジャッジ時間 | 14,989 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 33 |
ソースコード
import ioimport sysfrom collections import defaultdict, deque, Counterfrom itertools import permutations, combinations, accumulatefrom heapq import heappush, heappopfrom bisect import bisect_right, bisect_leftfrom math import gcdimport math_INPUT = """\64 5 31 2 4 21 2 13 4 22 4 51 3 22 3 7102 0 31 1 32 0 22 1 11 0 22 0 3"""INF=10**20def WF(cost):for k in range(len(cost)):for i in range(len(cost)):for j in range(len(cost)):if cost[i][k]!=INF and cost[k][j]!=INF:cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])return costclass BIT:def __init__(self, n):self._n = nself.data = [0] * ndef add(self, p, x):assert 0 <= p < self._np += 1while p <= self._n:self.data[p - 1] += xp += p & -p#合計にはrを含まないdef sum(self, l, r):assert 0 <= l <= r <= self._nreturn self._sum(r) - self._sum(l)def _sum(self, r):s = 0while r > 0:s += self.data[r - 1]r -= r & -rreturn s#pの位置をxという値にセットdef set(self, p, x):self.add(p, -self.sum(p, p+1) + x)def input():return sys.stdin.readline()[:-1]def solve(test):N,M,K=map(int, input().split())S=list(map(lambda x:int(x)-1, input().split()))cost=[[INF]*N for _ in range(N)]for i in range(N): cost[i][i]=0for i in range(M):a,b,c=map(int, input().split())cost[a-1][b-1]=ccost[b-1][a-1]=ccost=WF(cost)bit=BIT(K)for i in range(K): bit.add(i,cost[S[i]][S[i+1]])Q=int(input())for _ in range(Q):q=list(map(int, input().split()))if q[0]==1:a,b=q[1],q[2]-1S[a]=bif a<K: bit.set(a,cost[S[a]][S[a+1]])if a>0: bit.set(a-1,cost[S[a-1]][S[a]])else:l,r=q[1],q[2]print(bit.sum(l,r))def random_input():from random import randint,shuffleN=randint(1,10)M=randint(1,N)A=list(range(1,M+1))+[randint(1,M) for _ in range(N-M)]shuffle(A)return (" ".join(map(str, [N,M]))+"\n"+" ".join(map(str, A))+"\n")*3def simple_solve():return []def main(test):if test==0:solve(0)elif test==1:sys.stdin = io.StringIO(_INPUT)case_no=int(input())for _ in range(case_no):solve(0)else:for i in range(1000):sys.stdin = io.StringIO(random_input())x=solve(1)y=simple_solve()if x!=y:print(i,x,y)print(*[line for line in sys.stdin],sep='')break#0:提出用、1:与えられたテスト用、2:ストレステスト用main(0)