結果
問題 | No.2565 はじめてのおつかい |
ユーザー | McGregorsh |
提出日時 | 2023-12-20 22:56:33 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 274 ms / 2,000 ms |
コード長 | 13,109 bytes |
コンパイル時間 | 250 ms |
コンパイル使用メモリ | 81,828 KB |
実行使用メモリ | 105,400 KB |
最終ジャッジ日時 | 2023-12-20 22:56:51 |
合計ジャッジ時間 | 17,093 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 151 ms
90,296 KB |
testcase_01 | AC | 149 ms
90,296 KB |
testcase_02 | AC | 149 ms
90,296 KB |
testcase_03 | AC | 274 ms
105,272 KB |
testcase_04 | AC | 222 ms
105,400 KB |
testcase_05 | AC | 147 ms
90,296 KB |
testcase_06 | AC | 234 ms
94,520 KB |
testcase_07 | AC | 209 ms
92,472 KB |
testcase_08 | AC | 213 ms
94,264 KB |
testcase_09 | AC | 222 ms
93,624 KB |
testcase_10 | AC | 226 ms
94,392 KB |
testcase_11 | AC | 267 ms
99,256 KB |
testcase_12 | AC | 188 ms
91,960 KB |
testcase_13 | AC | 228 ms
93,624 KB |
testcase_14 | AC | 256 ms
97,208 KB |
testcase_15 | AC | 246 ms
96,568 KB |
testcase_16 | AC | 204 ms
102,072 KB |
testcase_17 | AC | 161 ms
91,192 KB |
testcase_18 | AC | 165 ms
91,576 KB |
testcase_19 | AC | 263 ms
97,976 KB |
testcase_20 | AC | 233 ms
97,720 KB |
testcase_21 | AC | 217 ms
97,848 KB |
testcase_22 | AC | 195 ms
95,032 KB |
testcase_23 | AC | 209 ms
95,288 KB |
testcase_24 | AC | 166 ms
91,448 KB |
testcase_25 | AC | 269 ms
99,128 KB |
testcase_26 | AC | 212 ms
95,032 KB |
testcase_27 | AC | 215 ms
98,744 KB |
testcase_28 | AC | 243 ms
98,104 KB |
testcase_29 | AC | 255 ms
100,280 KB |
testcase_30 | AC | 226 ms
99,256 KB |
testcase_31 | AC | 263 ms
98,104 KB |
testcase_32 | AC | 224 ms
95,544 KB |
testcase_33 | AC | 240 ms
99,128 KB |
testcase_34 | AC | 245 ms
97,976 KB |
testcase_35 | AC | 227 ms
100,536 KB |
testcase_36 | AC | 273 ms
100,024 KB |
testcase_37 | AC | 208 ms
94,904 KB |
testcase_38 | AC | 238 ms
97,208 KB |
testcase_39 | AC | 247 ms
96,568 KB |
testcase_40 | AC | 235 ms
99,896 KB |
testcase_41 | AC | 271 ms
101,688 KB |
testcase_42 | AC | 215 ms
95,032 KB |
testcase_43 | AC | 234 ms
96,824 KB |
testcase_44 | AC | 218 ms
94,776 KB |
testcase_45 | AC | 193 ms
92,856 KB |
testcase_46 | AC | 253 ms
97,208 KB |
testcase_47 | AC | 221 ms
93,496 KB |
testcase_48 | AC | 223 ms
94,136 KB |
testcase_49 | AC | 190 ms
92,088 KB |
testcase_50 | AC | 215 ms
93,240 KB |
testcase_51 | AC | 150 ms
90,296 KB |
testcase_52 | AC | 193 ms
91,960 KB |
ソースコード
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') import math from bisect import bisect_left, bisect_right, insort from typing import Generic, Iterable, Iterator, TypeVar, Union, 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) -> Union[T, None]: "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) -> Union[T, None]: "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) -> Union[T, None]: "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) -> Union[T, None]: "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 ###セグメントツリー### #####segfunc##### def segfunc(x, y): return min(x, y) # 最小値 min(x, y) # 最大値 max(x, y) # 区間和 x + y # 区間積 x * y # 最大公約数 math.gcd(x, y) # 排他的論理和 x ^ y ################# #####ide_ele##### ide_ele = float('inf') # 最小値 float('inf') # 最大値 -float('inf') # 区間和 0 # 区間積 1 # 最大公約数 0 # 排他的論理和 0 ################# class SegTree: """ init(init_val, ide_ele): 配列init_valで初期化 O(N) update(k, x): k番目の値をxに更新 O(logN) query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN) """ def __init__(self, init_val, segfunc, ide_ele): """ init_val: 配列の初期値 segfunc: 区間にしたい操作 ide_ele: 単位元 n: 要素数 num: n以上の最小の2のべき乗 tree: セグメント木(1-index) """ n = len(init_val) self.segfunc = segfunc self.ide_ele = ide_ele self.num = 1 << (n - 1).bit_length() self.tree = [ide_ele] * 2 * self.num # 配列の値を葉にセット for i in range(n): self.tree[self.num + i] = init_val[i] # 構築していく for i in range(self.num - 1, 0, -1): self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1]) def update(self, k, x): """ k番目の値をxに更新 k: index(0-index) x: update value """ k += self.num self.tree[k] = x while k > 1: self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1]) k >>= 1 def query(self, l, r): """ [l, r)のsegfuncしたものを得る l: index(0-index) r: index(0-index) """ res = self.ide_ele l += self.num r += self.num while l < r: if l & 1: res = self.segfunc(res, self.tree[l]) l += 1 if r & 1: res = self.segfunc(res, self.tree[r - 1]) l >>= 1 r >>= 1 return res ###UnionFind### class UnionFind: """0-indexed""" def __init__(self, n): self.n = n self.parent = [-1] * n self.__group_count = n # 辺がないとき、連結成分はn個あります def unite(self, x, y): """xとyをマージ""" x = self.root(x) y = self.root(y) if x == y: return 0 self.__group_count -= 1 # 木と木が合体するので、連結成分数が1減ります if self.parent[x] > self.parent[y]: x, y = y, x self.parent[x] += self.parent[y] self.parent[y] = x return self.parent[x] def is_same(self, x, y): """xとyが同じ連結成分か判定""" return self.root(x) == self.root(y) def root(self, x): """xの根を取得""" if self.parent[x] < 0: return x else: self.parent[x] = self.root(self.parent[x]) return self.parent[x] def size(self, x): """xが属する連結成分のサイズを取得""" return -self.parent[self.root(x)] def all_sizes(self) -> List[int]: """全連結成分のサイズのリストを取得 O(N) """ sizes = [] for i in range(self.n): size = self.parent[i] if size < 0: sizes.append(-size) return sizes def groups(self) -> List[List[int]]: """全連結成分の内容のリストを取得 O(N・α(N))""" groups = dict() for i in range(self.n): p = self.root(i) if not groups.get(p): groups[p] = [] groups[p].append(i) return list(groups.values()) def group_count(self) -> int: """連結成分の数を取得 O(1)""" return self.__group_count # 変数を返すだけなので、O(1)です ###素因数分解### def prime_factorize(n: int) -> list: return_list = [] while n % 2 == 0: return_list.append(2) n //= 2 f = 3 while f * f <= n: if n % f == 0: return_list.append(f) n //= f else: f += 2 if n != 1: return_list.append(n) return return_list ###n進数から10進数変換### def base_10(num_n,n): num_10 = 0 for s in str(num_n): num_10 *= n num_10 += int(s) return num_10 ###10進数からn進数変換### def base_n(num_10,n): str_n = '' while num_10: if num_10%n>=10: return -1 str_n += str(num_10%n) num_10 //= n return int(str_n[::-1]) ###複数の数の最大公約数、最小公倍数### from functools import reduce # 最大公約数 def gcd_list(num_list: list) -> int: return reduce(gcd, num_list) # 最小公倍数 def lcm_base(x: int, y: int) -> int: return (x * y) // gcd(x, y) def lcm_list(num_list: list): return reduce(lcm_base, num_list, 1) ###約数列挙### def make_divisors(n): lower_divisors, upper_divisors = [], [] i = 1 while i * i <= n: if n % i == 0: lower_divisors.append(i) if i != n // i: upper_divisors.append(n//i) i += 1 return lower_divisors + upper_divisors[::-1] ###順列### def nPr(n, r): npr = 1 for i in range(n, n-r, -1): npr *= i return npr ###組合せ### def nCr(n, r): factr = 1 r = min(r, n - r) for i in range(r, 1, -1): factr *= i return nPr(n, r)//factr ###組合せMOD### def comb(n,k): nCk = 1 MOD = 99824353 for i in range(n-k+1, n+1): nCk *= i nCk %= MOD for i in range(1,k+1): nCk *= pow(i,MOD-2,MOD) nCk %= MOD return nCk ###回転行列### def RotationMatrix(before_x, before_y, d): d = math.radians(d) new_x = before_x * math.cos(d) - before_y * math.sin(d) new_y = before_x * math.sin(d) + before_y * math.cos(d) return new_x, new_y ###ダイクストラ### def daikusutora(N, G, s): dist = [INF] * N que = [(0, s)] dist[s] = 0 while que: c, v = heappop(que) if dist[v] < c: continue for t, cost in G[v]: if dist[v] + cost < dist[t]: dist[t] = dist[v] + cost heappush(que, (dist[t], t)) return dist import sys from sys import stdin from fractions import Fraction import math from math import ceil, floor, sqrt, pi, factorial, gcd from copy import deepcopy from collections import Counter, deque, defaultdict from heapq import heapify, heappop, heappush from itertools import accumulate, product, combinations, combinations_with_replacement, permutations from bisect import bisect, bisect_left, bisect_right from functools import reduce, lru_cache from decimal import Decimal, getcontext, ROUND_HALF_UP def i_input(): return int(stdin.readline()) def i_map(): return map(int, stdin.readline().split()) def i_list(): return list(i_map()) def s_input(): return stdin.readline()[:-1] def s_map(): return s_input().split() def s_list(): return list(s_map()) def lcm(a, b): return a * b // gcd(a, b) def get_distance(x1, y1, x2, y2): d = sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2) return d def rotate(table): n_fild = [] for x in zip(*table[::-1]): n_fild.append(x) return n_fild sys.setrecursionlimit(10 ** 7) INF = float('inf') MOD = 10 ** 9 + 7 MOD2 = 998244353 alpa = 'abcdefghijklmnopqrstuvwxyz' ALPA = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' def main(): N, M = i_map() nums = [[] for _ in range(N)] for i in range(M): a, b = i_map() a -= 1 b -= 1 nums[a].append(b) one = [INF] * N one[0] = 0 que1 = deque() que1.append(0) while que1: a = que1.popleft() for nxt in nums[a]: if one[nxt] == INF: one[nxt] = one[a] + 1 que1.append(nxt) two = [INF] * N two[-2] = 0 que2 = deque() que2.append(N-2) while que2: a = que2.popleft() for nxt in nums[a]: if two[nxt] == INF: two[nxt] = two[a] + 1 que2.append(nxt) three = [INF] * N three[-1] = 0 que3 = deque() que3.append(N-1) while que3: a = que3.popleft() for nxt in nums[a]: if three[nxt] == INF: three[nxt] = three[a] + 1 que3.append(nxt) A = one[N-2] + two[N-1] + three[0] B = one[N-1] + three[N-2] + two[0] C = min(A, B) if C == INF: print(-1) else: print(C) if __name__ == '__main__': main()