Konrad and Company Evaluation (Codeforces 1229C)
Tags: Others, graphs

Konrad is a Human Relations consultant working for VoltModder, a large electrical equipment producer. Today, he has been tasked with evaluating the level of happiness in the company.There are $$$n$$$ people working for VoltModder, numbered from $$$1$$$ to $$$n$$$. Each employee earns a different amount of money in the company — initially, the $$$i$$$-th person earns $$$i$$$ rubles per day.On each of $$$q$$$ following days, the salaries will be revised. At the end of the $$$i$$$-th day, employee $$$v_i$$$ will start earning $$$n+i$$$ rubles per day and will become the best-paid person in the company. The employee will keep his new salary until it gets revised again.Some pairs of people don't like each other. This creates a great psychological danger in the company. Formally, if two people $$$a$$$ and $$$b$$$ dislike each other and $$$a$$$ earns more money than $$$b$$$, employee $$$a$$$ will brag about this to $$$b$$$. A dangerous triple is a triple of three employees $$$a$$$, $$$b$$$ and $$$c$$$, such that $$$a$$$ brags to $$$b$$$, who in turn brags to $$$c$$$. If $$$a$$$ dislikes $$$b$$$, then $$$b$$$ dislikes $$$a$$$.At the beginning of each day, Konrad needs to evaluate the number of dangerous triples in the company. Can you help him do it?

Input: The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 100\,000$$$, $$$0 \le m \le 100\,000$$$) — the number of employees in the company and the number of pairs of people who don't like each other. Each of the following $$$m$$$ lines contains two integers $$$a_i$$$, $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$a_i \neq b_i$$$) denoting that employees $$$a_i$$$ and $$$b_i$$$ hate each other (that is, $$$a_i$$$ dislikes $$$b_i$$$ and $$$b_i$$$ dislikes $$$a_i$$$). Each such relationship will be mentioned exactly once.The next line contains an integer $$$q$$$ ($$$0 \le q \le 100\,000$$$) — the number of salary revisions. The $$$i$$$-th of the following $$$q$$$ lines contains a single integer $$$v_i$$$ ($$$1 \le v_i \le n$$$) denoting that at the end of the $$$i$$$-th day, employee $$$v_i$$$ will earn the most.

Output: Output $$$q + 1$$$ integers. The $$$i$$$-th of them should contain the number of dangerous triples in the company at the beginning of the $$$i$$$-th day.

Note: Consider the first sample test. The $$$i$$$-th row in the following image shows the structure of the company at the beginning of the $$$i$$$-th day. A directed edge from $$$a$$$ to $$$b$$$ denotes that employee $$$a$$$ brags to employee $$$b$$$. The dangerous triples are marked by highlighted edges.  

Sample Inputs:
4 5
1 2
2 4
1 3
3 4
2 3
2
2
3

3 3
1 2
2 3
1 3
5
1
2
2
1
3

Sample Outputs:
4
3
2

1
1
1
1
1
1

Solution (Python):
import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
IN = [0] * n
OUT = [0] * n
INSET = [[] for i in range(n)]
for i in range(m):
    (x, y) = sorted(map(int, input().split()))
    IN[x - 1] += 1
    OUT[y - 1] += 1
    INSET[x - 1].append(y - 1)
ANS = 0
for i in range(n):
    ANS += IN[i] * OUT[i]
print(ANS)
Q = int(input())
for i in range(Q):
    q = int(input()) - 1
    ANS -= IN[q] * OUT[q]
    OUT[q] += IN[q]
    IN[q] = 0
    for x in INSET[q]:
        INSET[x].append(q)
        ANS += (IN[x] + 1) * (OUT[x] - 1) - IN[x] * OUT[x]
        IN[x] += 1
        OUT[x] -= 1
    INSET[q] = []
    print(ANS)

Solution (Python):
import sys
(n, m) = list(map(int, sys.stdin.readline().strip().split()))
L = [0 for i in range(0, n)]
H = [[] for i in range(0, n)]
for i in range(0, m):
    (x, y) = list(map(int, sys.stdin.readline().strip().split()))
    x = x - 1
    y = y - 1
    if x > y:
        (x, y) = (y, x)
    L[y] = L[y] + 1
    H[x].append(y)
ans = 0
for i in range(0, n):
    ans = ans + L[i] * len(H[i])
print(ans)
q = int(sys.stdin.readline().strip())
for i in range(0, q):
    v = int(sys.stdin.readline().strip()) - 1
    ans = ans - L[v] * len(H[v])
    L[v] = L[v] + len(H[v])
    while len(H[v]) > 0:
        w = H[v].pop()
        H[w].append(v)
        L[w] = L[w] - 1
        ans = ans + L[w] - len(H[w]) + 1
    print(ans)

Solution (Python):
(n, m) = map(int, input().split())
(out, inp) = ([0] * (n + 1), [0] * (n + 1))
inset = [[] for i in range(n + 1)]
for i in range(m):
    (x, y) = map(int, input().split())
    if x > y:
        z = x
        x = y
        y = z
    out[y] += 1
    inp[x] += 1
    inset[x].append(y)
q = int(input())
res = 0
for ind in range(1, n + 1):
    res += inp[ind] * out[ind]
print(res)
for i in range(q):
    best = int(input())
    res -= out[best] * inp[best]
    for pred_ind in inset[best]:
        res += -out[pred_ind] * inp[pred_ind] + (out[pred_ind] - 1) * (inp[pred_ind] + 1)
        out[pred_ind] -= 1
        inp[pred_ind] += 1
        inset[pred_ind].append(best)
    out[best] += inp[best]
    inp[best] = 0
    inset[best] = []
    print(res)