Problem:


Score : 1100 points

Problem Statement

You are given a directed graph with N vertices and M edges.
The vertices are numbered 1, 2, ..., N, and the edges are numbered 1, 2, ..., M.
Edge i points from Vertex a_i to Vertex b_i.

For each edge, determine whether the reversion of that edge would change the number of the strongly connected components in the graph.

Here, the reversion of Edge i means deleting Edge i and then adding a new edge that points from Vertex b_i to Vertex a_i.

Constraints

2 \leq N \leq 1000

1 \leq M \leq 200,000

1 \leq a_i, b_i \leq N

a_i \neq b_i

If i \neq j, then a_i \neq a_j or b_i \neq b_j.

Input

Input is given from Standard Input in the following format:

N M
a_1 b_1
a_2 b_2
:
a_M b_M

Output

Print M lines. In the i-th line, if the reversion of Edge i would change the number of the strongly connected components in the graph, print diff; if it would not, print same.

Sample Input 1

3 3
1 2
1 3
2 3

Sample Output 1

same
diff
same

The number of the strongly connected components is 3 without reversion of edges, but it will become 1 if Edge 2 is reversed.

Sample Input 2

2 2
1 2
2 1

Sample Output 2

diff
diff

Reversion of an edge may result in multiple edges in the graph.

Sample Input 3

5 9
3 2
3 1
4 1
4 2
3 5
5 3
3 4
1 2
2 5

Sample Output 3

same
same
same
same
same
diff
diff
diff
diff



Sample input:
3 3
1 2
1 3
2 3


Sample output:
same
diff
same

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    def dfs0(u, st=-1, en=-1):
        if en == -1:
            for i, ku in enumerate(to[u]):
                if can[u][ku][0] != -1: continue
                can[u][ku][0] = i
                dfs0(ku, u, i)
            return
        for ku in to[u]:
            if ku == st: continue
            if can[st][ku][0] != -1: continue
            can[st][ku][0] = en
            dfs0(ku, st, en)

    def dfs1(u, st=-1, en=-1):
        if en == -1:
            sz = len(to[u])
            for i, ku in enumerate(to[u][::-1]):
                if can[u][ku][1] != -1: continue
                can[u][ku][1] = sz - 1 - i
                dfs1(ku, u, sz - 1 - i)
            return
        for ku in to[u]:
            if ku == st: continue
            if can[st][ku][1] != -1: continue
            can[st][ku][1] = en
            dfs1(ku, st, en)

    to = defaultdict(list)
    n, m = map(int, input().split())
    ee = []
    for _ in range(m):
        a, b = map(int, input().split())
        a, b = a - 1, b - 1
        to[a].append(b)
        ee.append([a, b])
    for v in to.values():
        v.sort()
    #print(to)
    can = [[[-1] * 2 for _ in range(n)] for _ in range(n)]
    fin = [False] * n
    for u, v in ee:
        for w in [u, v]:
            if not fin[w]:
                fin[w] = True
                dfs0(w)
                dfs1(w)
        # print(u,v)
        # print(can[u][v][0] == can[u][v][1])
        # print(sum(can[v][u]) == -2)
        if (can[u][v][0] == can[u][v][1]) == (sum(can[v][u]) == -2):
            print("same")
        else:
            print("diff")
    #for x in can:
    #    print(x)

main()

Submission status: Runtime Error

Solution code:
import numpy as np


def main():
    n = int(input())
    a = [int(x) for x in input().split()]

    best, solution = int(-1e10), []
    for p in range(2):
        c = a.copy()

        indexes = list(range(p, n, 2))
        if len(indexes) == 0:
            continue

        maks = max([c[i] for i in indexes])
        pick = next((i for i in indexes if c[i] == maks))
        chosen = set([pick] if maks <= 0 else [i for i in indexes if c[i] > 0])
        is_chosen = [(i in chosen) for i in range(n)]

        tot, res = sum([c[i] for i in chosen]), []
        for i in reversed(range(n)):
            if not is_chosen[i]:
                if i == 0 or i + 1 == len(c):
                    res += [i]
                    del c[i], is_chosen[i]
                elif is_chosen[i - 1] == is_chosen[i + 1]:
                    res += [i]
                    c[i - 1] += c[i + 1]
                    del c[i + 1], c[i], is_chosen[i + 1], is_chosen[i]

        for end in [0, -1]:
            while len(c) > 1 and not is_chosen[end]:
                res += [end]
                del c[end], is_chosen[end]

        if tot > best:
            best, solution = tot, np.array(res) + 1

    print(best, len(solution), *solution, sep='\n')


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np


def main():
    n = int(input())
    a = [int(x) for x in input().split()]

    best, solution = int(-1e10), []
    for p in range(2):
        c = a.copy()

        indexes = list(range(p, n, 2))
        if len(indexes) == 0:
            continue

        maks = max([c[i] for i in indexes])
        pick = next((i for i in indexes if c[i] == maks))
        chosen = set([pick] if maks <= 0 else [i for i in indexes if c[i] > 0])
        is_chosen = [(i in chosen) for i in range(n)]

        tot, res = sum([c[i] for i in chosen]), []
        for i in reversed(range(n)):
            if not is_chosen[i]:
                if i == 0 or i + 1 == len(c):
                    res += [i]
                    del c[i], is_chosen[i]
                elif is_chosen[i - 1] == is_chosen[i + 1]:
                    res += [i]
                    c[i - 1] += c[i + 1]
                    del c[i + 1], c[i], is_chosen[i + 1], is_chosen[i]

        for end in [0]:
            while len(c) > 1 and not is_chosen[end]:
                res += [end]
                del c[end], is_chosen[end]

        if tot > best:
            best, solution = tot, np.array(res) + 1

    print(best, len(solution), *solution, sep='\n')


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np


def main():
    n = int(input())
    a = [int(x) for x in input().split()]

    best, solution = int(-1e10), []
    for p in range(2):
        c = a.copy()

        indexes = list(range(p, n, 2))
        if len(indexes) == 0:
            continue

        maks = max([c[i] for i in indexes])
        pick = next((i for i in indexes if c[i] == maks))
        chosen = set([pick] if maks <= 0 else [i for i in indexes if c[i] > 0])
        is_chosen = [(i in chosen) for i in range(n)]

        tot, res = sum([c[i] for i in chosen]), []
        for i in reversed(range(n)):
            if not is_chosen[i]:
                if i == 0 or i + 1 == len(c):
                    res += [i]
                    del c[i], is_chosen[i]
                elif is_chosen[i - 1] == is_chosen[i + 1]:
                    res += [i]
                    c[i - 1] += c[i + 1]
                    del c[i + 1], c[i], is_chosen[i + 1], is_chosen[i]

        for end in (0, ):
            while len(c) > 1 and not is_chosen[end]:
                res += [end]
                del c[end], is_chosen[end]

        if tot > best:
            best, solution = tot, np.array(res) + 1

    print(best, len(solution), *solution, sep='\n')


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np


def main():
    n = int(input())
    a = [int(x) for x in input().split()]

    best, solution = int(-1e10), []
    for p in range(2):
        c = a.copy()

        indexes = list(range(p, n, 2))
        if len(indexes) == 0:
            continue

        maks = max([c[i] for i in indexes])
        pick = next((i for i in indexes if c[i] == maks))
        chosen = set([pick] if maks <= 0 else [i for i in indexes if c[i] > 0])
        is_chosen = [(i in chosen) for i in range(n)]

        tot, res = sum([c[i] for i in chosen]), []
        for i in reversed(range(n)):
            if not is_chosen[i]:
                if i == 0 or i + 1 == len(c):
                    res += [i]
                    del c[i], is_chosen[i]
                elif is_chosen[i - 1] == is_chosen[i + 1]:
                    res += [i]
                    c[i - 1] += c[i + 1]
                    del c[i + 1], c[i], is_chosen[i + 1], is_chosen[i]

        for end in (0):
            while len(c) > 1 and not is_chosen[end]:
                res += [end]
                del c[end], is_chosen[end]

        if tot > best:
            best, solution = tot, np.array(res) + 1

    print(best, len(solution), *solution, sep='\n')


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3


class UnionFind():
    def __init__(self, size):
        self.table = [-1] * size

    def find(self, x):
        while 0 <= self.table[x]:
            x = self.table[x]
        return x

    def unite(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            dx = -self.table[rx]
            dy = -self.table[ry]
            if dx != dy:
                if dx < dy:
                    self.table[rx] = ry
                else:
                    self.table[ry] = rx
            else:
                self.table[rx] -= 1
                self.table[ry] = rx
        return


e = None
re = None


post = None
rev = None
cc = None
scc = None

t = 1

def dfs0(u, r):
    global post, rev, t
    global cc

    cc.unite(u, r)
    post[u] = 1  # dummy
    for w in e[u]:
        if post[w] == 0:
            dfs0(w, r)
    post[u] = t
    rev[t] = u
    t += 1


def dfs1(u, r, cr, visited):
    global scc

    scc.unite(u, r)
    visited[u] = True
    for w in re[u]:
        if cc.find(w) != cr:
            continue
        if not visited[w]:
            dfs1(w, r, cr, visited)


def dfs2(u, r, first, rs, visited):

    visited[u] = True
    for w in e[u]:
        if not visited[w]:
            dfs2(w, r, first, rs, visited)
        elif w != r and w != first:
            rs.add((r, w))


def traverse(n, s, rs):
    visited = [False] * (n + 1)
    visited[s] = True
    for w in e[s]:
        visited[w] = True
    for w in e[s]:
        dfs2(w, s, w, rs, visited)


def solve(n, m, edges):
    global post, rev
    global cc, scc

    post = [0] * (n + 1)
    rev = [0] * (n + 1)
    cc = UnionFind(n + 1)
    scc = UnionFind(n + 1)

    visited = [False] * (n + 1)
    for r in range(1, n + 1):
        if post[r] == 0:
            cur = t
            dfs0(r, r)
            for v in range(t - 1, cur - 1, -1):
                r1 = rev[v]
                if not visited[r1]:
                    cr = cc.find(r1)
                    dfs1(r1, r1, cr, visited)

    visited = [False] * (n + 1)
    path_exists = set()
    for a, b in edges:
        if not visited[a]:
            visited[a] = True
            traverse(n, a, path_exists)


    for a, b in edges:
        scc_a = scc.find(a)
        scc_b = scc.find(b)
        exist = (a, b) in path_exists
        print('diff' if (scc_a == scc_b) ^ exist else 'same')


def main():
    global e, re

    n, m = input().split()
    n = int(n)
    m = int(m)
    edges = []
    e = [[] for _ in range(n + 1)]
    re = [[] for _ in range(n + 1)]
    for i in range(m):
        a, b = input().split()
        a = int(a)
        b = int(b)
        edges.append((a, b))
        e[a].append(b)
        re[b].append(a)


    solve(n, m, edges)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3


class UnionFind():
    def __init__(self, size):
        self.table = [-1] * size

    def find(self, x):
        while 0 <= self.table[x]:
            x = self.table[x]
        return x

    def unite(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            dx = -self.table[rx]
            dy = -self.table[ry]
            if dx != dy:
                if dx < dy:
                    self.table[rx] = ry
                else:
                    self.table[ry] = rx
            else:
                self.table[rx] -= 1
                self.table[ry] = rx
        return


e = None
re = None


post = None
rev = None
cc = None
scc = None

t = 1

def dfs0(u, r):
    global post, rev, t
    global cc

    cc.unite(u, r)
    post[u] = 1  # dummy
    for w in e[u]:
        if post[w] == 0:
            dfs0(w, r)
    post[u] = t
    rev[t] = u
    t += 1


def dfs1(u, r, cr, visited):
    global scc

    scc.unite(u, r)
    visited[u] = True
    for w in re[u]:
        if cc.find(w) != cr:
            continue
        if not visited[w]:
            dfs1(w, r, cr, visited)


def dfs2(u, r, rs, visited):
    visited[u] = True
    for w in e[u]:
        if w != r and not w in rs:
            rs.add(w)
        if not visited[w]:
            dfs2(w, r, rs, visited)


def find_another_paths(n, s, rs):
    for w in e[s]:
        visited = [False] * (n + 1)
        visited[s] = True
        dfs2(w, w, rs, visited)


def solve(n, m, edges):
    global post, rev
    global cc, scc

    post = [0] * (n + 1)
    rev = [0] * (n + 1)
    cc = UnionFind(n + 1)
    scc = UnionFind(n + 1)
    visited = [False] * (n + 1)

    for r in range(1, n + 1):
        if post[r] == 0:
            cur = t
            dfs0(r, r)
            for v in range(t - 1, cur - 1, -1):
                r1 = rev[v]
                if not visited[r1]:
                    cr = cc.find(r1)
                    dfs1(r1, r1, cr, visited)

    another_paths = [None] * (n + 1)
    for a, b in edges:
        if another_paths[a] is None:
            another_paths[a] = set()
            find_another_paths(n, a, another_paths[a])


    for a, b in edges:
        scc_a = scc.find(a)
        scc_b = scc.find(b)
        exist = b in another_paths[a]
        print('diff' if (scc_a == scc_b) ^ exist else 'same')


def main():
    global e, re

    n, m = input().split()
    n = int(n)
    m = int(m)
    edges = []
    e = [[] for _ in range(n + 1)]
    re = [[] for _ in range(n + 1)]
    for i in range(m):
        a, b = input().split()
        a = int(a)
        b = int(b)
        edges.append((a, b))
        e[a].append(b)
        re[b].append(a)


    solve(n, m, edges)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3


class UnionFind():
    def __init__(self, size):
        self.table = [-1] * size

    def find(self, x):
        while 0 <= self.table[x]:
            x = self.table[x]
        return x

    def unite(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            dx = -self.table[rx]
            dy = -self.table[ry]
            if dx != dy:
                if dx < dy:
                    self.table[rx] = ry
                else:
                    self.table[ry] = rx
            else:
                self.table[rx] -= 1
                self.table[ry] = rx
        return


e = None
re = None


post = None
rev = None
cc = None
scc = None

t_post = 1

def dfs0(u, r):
    global post, rev, t_post
    global cc

    cc.unite(u, r)
    post[u] = 1  # dummy
    for w in e[u]:
        if post[w] == 0:
            dfs0(w, r)
    post[u] = t_post
    rev[t_post] = u
    t_post += 1


def dfs1(u, r, cr, visited):
    global scc

    scc.unite(u, r)
    visited[u] = True
    for w in re[u]:
        if cc.find(w) != cr:
            continue
        if not visited[w]:
            dfs1(w, r, cr, visited)


def dfs2(u, t, visited):

    visited[u] = True
    for w in e[u]:
        if w == t:
            return True
        if not visited[w]:
            r = dfs2(w, t, visited)
            if r:
                return True

    return False


def find_another_path(n, s, t):
    visited = [False] * (n + 1)
    visited[s] = True
    for i in e[s]:
        if i != t:
            r = dfs2(i, t, visited)
            if r:
                return True

    return False


def solve(n, m, edges):
    global post, rev
    global cc, scc

    post = [0] * (n + 1)
    rev = [0] * (n + 1)
    cc = UnionFind(n + 1)
    scc = UnionFind(n + 1)
    visited = [False] * (n + 1)

    for r in range(1, n + 1):
        if post[r] == 0:
            cur = t_post
            dfs0(r, r)
            for v in range(t_post - 1, cur - 1, -1):
                r1 = rev[v]
                if not visited[r1]:
                    cr = cc.find(r1)
                    dfs1(r1, r1, cr, visited)

    for a, b in edges:
        scc_a = scc.find(a)
        scc_b = scc.find(b)
        pathf = find_another_path(n, a, b)
        print('diff' if (scc_a == scc_b) ^ pathf else 'same')


def main():
    global e, re

    n, m = input().split()
    n = int(n)
    m = int(m)
    edges = []
    e = [[] for _ in range(n + 1)]
    re = [[] for _ in range(n + 1)]
    for i in range(m):
        a, b = input().split()
        a = int(a)
        b = int(b)
        edges.append((a, b))
        e[a].append(b)
        re[b].append(a)


    solve(n, m, edges)


if __name__ == '__main__':
    main()