| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 476914 | 2021-09-29T04:59:32 Z | fufu | Regions (IOI09_regions) | Python 3 | 8000 ms | 131076 KB |
import resource, sys resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1)) sys.setrecursionlimit(10**6) def add(x, v): global n, bit x += 1 while x <= n: bit[x] += v x += x & (-x) def qry(x): global bit ret = 0 x += 1 while x > 0: ret += bit[x] x -= x & (-x) return ret def dfs(c): global p, l, r, g r[c] = l[c] for i in g[c]: if i != p[c]: l[i] = r[c] + 1 r[c] = dfs(i) return r[c] def main(): global n n, k, q = map(int, input().split()) m = 447 #sqrt const t = 0 global p, l, r, bit, g a = [0] * n p = [0] * n dp = [0] * n l = [0] * n r = [0] * n bit = [0] * (n + 1) b = [0] * k f1 = [[0 for j in range(k)] for i in range(m)] f2 = [[0 for j in range(k)] for i in range(m)] g = [[] for i in range(n)] w = [[] for i in range(k)] for i in range(n): if i: p[i], a[i] = map(int, input().split()) p[i] -= 1 g[p[i]].append(i) else: p[i] = -1 a[i] = int(input()) a[i] -= 1 w[a[i]].append(i) for i in range(k): if len(w[i]) > m: for j in range(n): if a[j] == i: dp[j] = 1 if p[j] != -1: dp[j] += dp[p[j]] f1[t][a[j]] += dp[j] dp = [0] * (n + 1) for j in reversed(range(n)): if a[j] == i: dp[j] += 1 f2[t][a[j]] += dp[j] if p[j] != -1: dp[p[j]] += dp[j] b[i] = t t += 1 else: b[i] = -1 dfs(0) for qq in range(q): x, y = map(int, input().split()) x -= 1 y -= 1 if b[x] != -1: print(f1[b[x]][y]) elif b[y] != -1: print(f2[b[y]][x]) else: ret = 0 for i in w[y]: add(l[i], 1) for i in w[x]: ret += qry(r[i]) - qry(l[i] - 1) for i in w[y]: add(l[i], -1) print(ret) main()
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 18 ms | 3252 KB | Output is correct |
| 2 | Correct | 17 ms | 3144 KB | Output is correct |
| 3 | Correct | 25 ms | 3264 KB | Output is correct |
| 4 | Correct | 41 ms | 3484 KB | Output is correct |
| 5 | Correct | 92 ms | 3720 KB | Output is correct |
| 6 | Correct | 105 ms | 5952 KB | Output is correct |
| 7 | Correct | 288 ms | 4776 KB | Output is correct |
| 8 | Correct | 357 ms | 5200 KB | Output is correct |
| 9 | Correct | 836 ms | 10800 KB | Output is correct |
| 10 | Correct | 1771 ms | 9148 KB | Output is correct |
| 11 | Correct | 4970 ms | 9492 KB | Output is correct |
| 12 | Correct | 5108 ms | 15268 KB | Output is correct |
| 13 | Execution timed out | 8015 ms | 11644 KB | Time limit exceeded |
| 14 | Execution timed out | 8031 ms | 12220 KB | Time limit exceeded |
| 15 | Execution timed out | 8066 ms | 49400 KB | Time limit exceeded |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 1968 ms | 37136 KB | Execution failed because the return code was nonzero |
| 2 | Runtime error | 1896 ms | 26276 KB | Execution failed because the return code was nonzero |
| 3 | Runtime error | 1625 ms | 58844 KB | Execution failed because the return code was nonzero |
| 4 | Execution timed out | 8090 ms | 41716 KB | Time limit exceeded |
| 5 | Execution timed out | 8080 ms | 71900 KB | Time limit exceeded |
| 6 | Incorrect | 6979 ms | 89800 KB | Output isn't correct |
| 7 | Execution timed out | 8083 ms | 107068 KB | Time limit exceeded |
| 8 | Runtime error | 7905 ms | 131076 KB | Execution killed with signal 9 |
| 9 | Runtime error | 872 ms | 131076 KB | Execution killed with signal 9 |
| 10 | Runtime error | 740 ms | 131076 KB | Execution killed with signal 9 |
| 11 | Runtime error | 724 ms | 131076 KB | Execution killed with signal 9 |
| 12 | Runtime error | 794 ms | 131076 KB | Execution killed with signal 9 |
| 13 | Runtime error | 790 ms | 131076 KB | Execution killed with signal 9 |
| 14 | Runtime error | 715 ms | 131076 KB | Execution killed with signal 9 |
| 15 | Runtime error | 723 ms | 131076 KB | Execution killed with signal 9 |
| 16 | Runtime error | 730 ms | 131076 KB | Execution killed with signal 9 |
| 17 | Runtime error | 712 ms | 131076 KB | Execution killed with signal 9 |