結果
問題 | No.826 連絡網 |
ユーザー | c-yan |
提出日時 | 2021-01-16 00:02:49 |
言語 | Go (1.22.1) |
結果 |
AC
|
実行時間 | 166 ms / 2,000 ms |
コード長 | 2,106 bytes |
コンパイル時間 | 14,545 ms |
コンパイル使用メモリ | 208,964 KB |
実行使用メモリ | 79,056 KB |
最終ジャッジ日時 | 2023-08-17 19:19:18 |
合計ジャッジ時間 | 15,219 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 2 ms
4,380 KB |
testcase_04 | AC | 2 ms
4,380 KB |
testcase_05 | AC | 1 ms
4,376 KB |
testcase_06 | AC | 2 ms
4,376 KB |
testcase_07 | AC | 2 ms
4,376 KB |
testcase_08 | AC | 2 ms
4,376 KB |
testcase_09 | AC | 2 ms
4,380 KB |
testcase_10 | AC | 1 ms
4,376 KB |
testcase_11 | AC | 2 ms
4,376 KB |
testcase_12 | AC | 70 ms
32,508 KB |
testcase_13 | AC | 28 ms
16,008 KB |
testcase_14 | AC | 52 ms
26,316 KB |
testcase_15 | AC | 7 ms
7,044 KB |
testcase_16 | AC | 30 ms
18,068 KB |
testcase_17 | AC | 28 ms
16,004 KB |
testcase_18 | AC | 22 ms
15,988 KB |
testcase_19 | AC | 79 ms
34,584 KB |
testcase_20 | AC | 75 ms
34,580 KB |
testcase_21 | AC | 2 ms
4,380 KB |
testcase_22 | AC | 37 ms
22,156 KB |
testcase_23 | AC | 59 ms
38,576 KB |
testcase_24 | AC | 13 ms
9,596 KB |
testcase_25 | AC | 166 ms
79,056 KB |
testcase_26 | AC | 16 ms
11,656 KB |
testcase_27 | AC | 67 ms
32,512 KB |
testcase_28 | AC | 55 ms
30,424 KB |
testcase_29 | AC | 25 ms
16,004 KB |
testcase_30 | AC | 118 ms
48,988 KB |
testcase_31 | AC | 40 ms
26,268 KB |
ソースコード
package main import ( "bufio" "fmt" "os" "strconv" ) func find(parent []int, i int) int { if parent[i] < 0 { return i } parent[i] = find(parent, parent[i]) return parent[i] } func unite(parent []int, i, j int) { i = find(parent, i) j = find(parent, j) if i == j { return } parent[j] += parent[i] parent[i] = j } func isqrt(n int) int { if n < 0 { panic("isqrt argument must be nonnegative") } if n <= 1 { return n } ok := 0 ng := 3037000500 // 3037000499 * 3037000499 < math.MaxInt64 < 3037000500 * 3037000500 if n < ng { ng = n } for ng-ok > 1 { m := ok + (ng-ok)/2 if m*m <= n { ok = m } else { ng = m } } return ok } func makePrimeTable(n int) []int { sieve := make([]int, n+1) for i := 0; i < n+1; i++ { sieve[i] = i } sieve[0] = -1 sieve[1] = -1 for i := 4; i < n+1; i += 2 { sieve[i] = 2 } for i := 3; i < isqrt(n)+1; i += 2 { if sieve[i] != i { continue } for j := i * i; j < n+1; j += i * 2 { if sieve[j] == j { sieve[j] = i } } } return sieve } func main() { defer flush() N := readInt() P := readInt() parent := make([]int, N+1) for i := 0; i < N+1; i++ { parent[i] = -1 } sieve := makePrimeTable(N) for j := 2 * 2; j < N+1; j += 2 { unite(parent, 2, j) } for i := 3; i < N+1; i++ { if sieve[i] != i { continue } if 2*i <= N { unite(parent, 2, i) } for j := i * i; j < N+1; j += i * 2 { unite(parent, i, j) } } println(-parent[find(parent, P)]) } const ( ioBufferSize = 1 * 1024 * 1024 // 1 MB ) var stdinScanner = func() *bufio.Scanner { result := bufio.NewScanner(os.Stdin) result.Buffer(make([]byte, ioBufferSize), ioBufferSize) result.Split(bufio.ScanWords) return result }() func readString() string { stdinScanner.Scan() return stdinScanner.Text() } func readInt() int { result, err := strconv.Atoi(readString()) if err != nil { panic(err) } return result } var stdoutWriter = bufio.NewWriter(os.Stdout) func flush() { stdoutWriter.Flush() } func println(args ...interface{}) (int, error) { return fmt.Fprintln(stdoutWriter, args...) }