oj.uz

Submission #206770

# Submission time Handle Problem Language Result Execution time Memory
206770 2020-03-05T08:09:18 Z Kamisama Election Campaign (JOI15_election_campaign) PyPy
0 / 100
 1000 ms 75024 KB 
import sys
input = sys.stdin.readline
maxn, logn = 10**5 + 7, 19
class Query:
    def __init__(self, a = 0, b = 0, c = 0):
        self.a, self.b, self.c = a, b, c
class Fenwick_tree:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * n
    def update(self, x, val):
        while(x <= self.n):
            self.bit[x] += val
            x += x & -x
    def get(self, x):
        res = 0
        while(x):
            res += self.bit[x]
            x -= x & -x
        return res
lv, par, timeIn, timeOut, dp = [0] * maxn, [0] * maxn, [0] * maxn, [0] * maxn, [0] * maxn
adj, road = [[] for i in range(maxn)], [[] for i in range(maxn)]
f= [[0 for i in range(logn)] for j in range(maxn)]
q = [Query()] * maxn
bit, nVisit = Fenwick_tree(maxn), 0
def dfs(u, p):
    global nVisit
    nVisit += 1
    f[u][0], par[u], timeIn[u] = p, p, nVisit
    for i in range(1, logn):
        v = f[u][i - 1]
        f[u][i] = -1 if(v == -1) else f[v][i - 1]
    for v in adj[u]:
        if(v != p):
            lv[v] = lv[u] + 1
            dfs(v, u)
    timeOut[u] = nVisit
def jump(u, k):
    cur = 0
    while(k):
        if(k & 1):
            u = f[u][cur]
        cur += 1
        k >>= 1
    return u
def lca(u, v):
    if(lv[v] < lv[u]):
        u, v = v, u
    v = jump(v, lv[v] - lv[u])
    if(u == v):
        return u
    for i in reversed(range(logn)):
        if(f[u][i] != f[v][i]):
            u, v = f[u][i], f[v][i]
    return par[u]
def solve(u, p):
    sumChild = 0
    for v in adj[u]:
        if(v != p):
            solve(v, u)
            sumChild += dp[v]
    dp[u] = sumChild
    for i in road[u]:
        dp[u] = max(dp[u], sumChild - bit.get(timeIn[q[i].a]) - bit.get(timeIn[q[i].b]) + q[i].c)
    bit.update(timeIn[u], dp[u] - sumChild)
    bit.update(timeOut[u] + 1, sumChild - dp[u])
n = int(input())
for i in range(1, n):
    u, v = map(int, input().split())
    adj[u].append(v)
    adj[v].append(u)
dfs(1, -1)
m = int(input())
for i in range(m):
    a, b, c = map(int, input().split())
    q[i] =  Query(a, b, c)
    road[lca(q[i].a, q[i].b)].append(i)
solve(1, -1)
print(dp[1])

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 44292 KB Output is correct
2 Correct 142 ms 41860 KB Output is correct
3 Correct 137 ms 41864 KB Output is correct
4 Correct 189 ms 44164 KB Output is correct
5 Correct 630 ms 58248 KB Output is correct
6 Runtime error 345 ms 57348 KB Execution failed because the return code was nonzero
7 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 41736 KB Output is correct
2 Correct 139 ms 41836 KB Output is correct
3 Correct 208 ms 45768 KB Output is correct
4 Runtime error 333 ms 56968 KB Execution failed because the return code was nonzero
5 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 41736 KB Output is correct
2 Correct 139 ms 41836 KB Output is correct
3 Correct 208 ms 45768 KB Output is correct
4 Runtime error 333 ms 56968 KB Execution failed because the return code was nonzero
5 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1026 ms 75024 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 44292 KB Output is correct
2 Correct 142 ms 41860 KB Output is correct
3 Correct 137 ms 41864 KB Output is correct
4 Correct 189 ms 44164 KB Output is correct
5 Correct 630 ms 58248 KB Output is correct
6 Runtime error 345 ms 57348 KB Execution failed because the return code was nonzero
7 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 44292 KB Output is correct
2 Correct 142 ms 41860 KB Output is correct
3 Correct 137 ms 41864 KB Output is correct
4 Correct 189 ms 44164 KB Output is correct
5 Correct 630 ms 58248 KB Output is correct
6 Runtime error 345 ms 57348 KB Execution failed because the return code was nonzero
7 Halted 0 ms 0 KB -