Problem:


Score : 800 points

Problem Statement

There is a directed graph with N vertices and N edges. The vertices are numbered 1, 2, ..., N.

The graph has the following N edges: (p_1, 1), (p_2, 2), ..., (p_N, N), and the graph is weakly connected. Here, an edge from Vertex u to Vertex v is denoted by (u, v), and a weakly connected graph is a graph which would be connected if each edge was bidirectional.

We would like to assign a value to each of the vertices in this graph so that the following conditions are satisfied. Here, a_i is the value assigned to Vertex i.

Each a_i is a non-negative integer.

For each edge (i, j), a_i \neq a_j holds.

For each i and each integer x(0 ≤ x < a_i), there exists a vertex j such that the edge (i, j) exists and x = a_j holds.

Determine whether there exists such an assignment.

Constraints

2 ≤ N ≤ 200 000

1 ≤ p_i ≤ N

p_i \neq i

The graph is weakly connected.

Input

Input is given from Standard Input in the following format:

N
p_1 p_2 ... p_N

Output

If the assignment is possible, print POSSIBLE; otherwise, print IMPOSSIBLE.

Sample Input 1

4
2 3 4 1

Sample Output 1

POSSIBLE

The assignment is possible: {a_i} = {0, 1, 0, 1} or {a_i} = {1, 0, 1, 0}.

Sample Input 2

3
2 3 1

Sample Output 2

IMPOSSIBLE

Sample Input 3

4
2 3 1 1

Sample Output 3

POSSIBLE

The assignment is possible: {a_i} = {2, 0, 1, 0}.

Sample Input 4

6
4 5 6 5 6 4

Sample Output 4

IMPOSSIBLE



Sample input:
4
2 3 4 1


Sample output:
POSSIBLE

Submission status: Runtime Error

Solution code:
from collections import deque

N=int(input())
IN=[[] for i in range(N)]
OUT=[-1 for i in range(N)]
p=list(map(int,input().split()))
for i in range(N):
    IN[p[i]-1].append(i)
    OUT[i]=p[i]-1

deg=[len(IN[i]) for i in range(N)]

deq=deque([v for v in range(N) if deg[v]==0])
res=[]
while deq:
    v=deq.popleft()
    res.append(v)
    deg[OUT[v]]-=1
    if deg[OUT[v]]==0:
        deq.append(OUT[v])

if len(res)==N:
    exit(print("POSSIBLE"))

start=-1
for i in range(N):
    if deg[i]>0:
        start=i
        break

cycle=[start]
while True:
    nv=OUT[cycle[-1]]
    if nv!=start:
        cycle.append(nv)
    else:
        break


dp=[-1]*N
for i in range(len(res)):
    v=res[i]
    mex=[False]*(len(IN[v])+1)
    for pv in IN[v]:
        if dp[pv]<=len(IN[v]):
            mex[dp[pv]]=True
    for i in range(len(mex)):
        if not mex[i]:
            dp[v]=i
            break

m0=-1
m1=-1
mex=[False]*(len(IN[start])+2)
for pv in IN[start]:
    if dp[pv]!=-1 and (dp[pv]<=len(IN[v])+1):
        mex[dp[pv]]=True
for i in range(len(mex)):
    if not mex[i]:
        if m0==-1:
            m0=i
        else:
            m1=i
            break

#m0
dp[start]=m0
for i in range(1,len(cycle)):
    v=cycle[i]
    mex=[False]*(len(IN[v])+1)
    for pv in IN[v]:
        if dp[pv]<=len(IN[v]):
            mex[dp[pv]]=True
    for i in range(len(mex)):
        if not mex[i]:
            dp[v]=i
            break
mex=[False]*(len(IN[start])+2)
for pv in IN[start]:
    if dp[pv]!=-1 and (dp[pv]<=len(IN[v])+1):
        mex[dp[pv]]=True
if not mex[m0]:
    exit(print("POSSIBLE"))

for v in cycle:
    dp[v]=-1

#m1
dp[start]=m1
for i in range(1,len(cycle)):
    v=cycle[i]
    mex=[False]*(len(IN[v])+1)
    for pv in IN[v]:
        if dp[pv]<=len(IN[v]):
            mex[dp[pv]]=True
    for i in range(len(mex)):
        if not mex[i]:
            dp[v]=i
            break
mex=[False]*(len(IN[start])+2)
for pv in IN[start]:
    if dp[pv]!=-1 and (dp[pv]<=len(IN[v])+1):
        mex[dp[pv]]=True
if not mex[m1]:
    exit(print("POSSIBLE"))

print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
from collections import deque

N=int(input())
IN=[[] for i in range(N)]
OUT=[-1 for i in range(N)]
p=list(map(int,input().split()))
for i in range(N):
    IN[p[i]-1].append(i)
    OUT[i]=p[i]-1

deg=[len(IN[i]) for i in range(N)]

deq=deque([v for v in range(N) if deg[v]==0])
res=[]
while deq:
    v=deq.popleft()
    res.append(v)
    deg[OUT[v]]-=1
    if deg[OUT[v]]==0:
        deq.append(OUT[v])

if len(res)==N:
    exit(print("POSSIBLE"))

start=-1
for i in range(N):
    if deg[i]>0:
        start=i
        break

cycle=[start]
while True:
    nv=OUT[cycle[-1]]
    if nv!=start:
        cycle.append(nv)
    else:
        break


dp=[-1]*N
for v in res:
    mex=[False]*(len(IN[v])+1)
    for pv in IN[v]:
        if dp[pv]<=len(IN[v]):
            mex[dp[pv]]=True
    for i in range(len(mex)):
        if not mex[i]:
            dp[v]=i
            break

m0=-1
m1=-1
mex=[False]*(len(IN[start])+2)
for pv in IN[start]:
    if dp[pv]!=-1 and dp[pv]<=len(IN[v])+1:
        mex[dp[pv]]=True
for i in range(len(mex)):
    if not mex[i]:
        if m0==-1:
            m0=i
        else:
            m1=i
            break

#m0
dp[start]=m0
for i in range(1,len(cycle)):
    v=cycle[i]
    temp=-1
    mex=[False]*(len(IN[v])+1)
    for pv in IN[v]:
        if dp[pv]<=len(IN[v]):
            mex[dp[pv]]=True
    for i in range(len(mex)):
        if not mex[i]:
            dp[v]=i
            break
mex=[False]*(len(IN[start])+2)
for pv in IN[start]:
    if dp[pv]!=-1 and dp[pv]<=len(IN[v])+1:
        mex[dp[pv]]=True
if not mex[dp[start]]:
    exit(print("POSSIBLE"))

for v in cycle:
    dp[v]=-1

#m1
dp[start]=m1
for i in range(1,len(cycle)):
    v=cycle[i]
    temp=-1
    mex=[False]*(len(IN[v])+1)
    for pv in IN[v]:
        if dp[pv]<=len(IN[v]):
            mex[dp[pv]]=True
    for i in range(len(mex)):
        if not mex[i]:
            dp[v]=i
            break
mex=[False]*(len(IN[start])+2)
for pv in IN[start]:
    if dp[pv]!=-1 and dp[pv]<=len(IN[v])+1:
        mex[dp[pv]]=True
if not mex[dp[start]]:
    exit(print("POSSIBLE"))

print("IMPOSSIBLE")

Submission status: Runtime Error

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

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18

N = input()
p = map(int, raw_input().split())
E = [[] for i in range(N + 1)]
for i in range(N):
    E[p[i]].append(i + 1)

flag = [True] * (N + 2)

def func(pos, pre, start, grundy):
    if grundy[pos] != -1:
        return grundy[pos]
    if pos == start and pre != -1:
        return INF
    ret = [func(to, pos, start, grundy) for to in E[pos]]
    if INF in ret:
        grundy[pos] = INF
        return INF
    for num in ret:
        flag[num] = False
    for i in range(N + 1):
        if flag[i]:
            grundy[pos] = i
            val = i
            break
    for num in ret:
        flag[num] = True
    return val

def func2(pos, grundy):
    if grundy[pos] != -1 and grundy[pos] != INF:
        return grundy[pos]
    ret = [func2(to, grundy) for to in E[pos]]
    for num in ret:
        flag[num] = False
    for i in range(N + 1):
        if flag[i]:
            grundy[pos] = i
            val = i
            break
    for num in ret:
        flag[num] = True
    return val

grundy = [-1] * (N + 1)

for i in range(N + 1):
    if grundy[i] == -1:
        ret = func(i, -1, i, grundy)
        if ret == INF:
            pos = i
            break

ff = [True] * (N + 2)
nex = 0
for to in E[pos]:
    ff[grundy[to]] = False
    if grundy[to] == INF:
        nex = to
cnt = 0
for i in range(N + 2):
    if ff[i]:
        grundy_ = list(grundy)
        grundy_[pos] = i
        func2(nex, grundy_)
        #print grundy_
        if cnt == 0:
            pre = grundy_[pos]
            if grundy_[pos] != grundy_[nex]:
                print "POSSIBLE"
                exit()
        if cnt == 1:
            if grundy_[nex] == pre:
                print "POSSIBLE"
            else:
                print "IMPOSSIBLE"
            exit()
        cnt += 1

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import heapq as hq


def helper(n):
    q = child_L[n]
    del child_L[n]

    hq.heapify(q)
    i = 0
    while q:
        t = hq.heappop(q)
        if i < t:
            break
        else:
            i += (i == t)

    j = i + 1
    while q:
        t = hq.heappop(q)
        if j < t:
            break
        else:
            j += (j == t)

    return (i, j)


if __name__ == '__main__':

    N = int(input())
    P = list(map(lambda x: int(x) - 1, input().split()))
    # D:出している辺の本数
    D = [0] * N
    for p in P:
        D[p] += 1
    # print(D)
    child_L = defaultdict(list)
    # S:辺を出してないものリスト
    S = [p for p in range(N) if D[p] == 0]

    L = [None] * N

    while S:
        # print(child_L)
        n = S.pop()

        q = child_L[n]
        print(q)
        del child_L[n]

        # listのqをヒープキューに変換
        hq.heapify(q)
        i = 0
        while q:
            t = hq.heappop(q)
            if i < t:
                break
            else:
                i += (i == t)

        L[n] = i
        print(L)
        m = P[n]
        print("m:" + str(m))
        child_L[m].append(i)
        D[m] -= 1
        if D[m] == 0:
            S.append(m)

    print(D)
    # cycle check
    try:
        start = D.index(1)
    except ValueError:
        print('POSSIBLE')
        exit()

    s1, s2 = helper(start)
    G = []
    n = P[start]
    while n != start:
        G.append(helper(n))
        n = P[n]

    # del N, P, D, child_L, S, L

    # 可能な初期値をそれぞれシミュレート
    # 1
    n = s1
    for g in G:
        if g[0] == n:
            n = g[1]
        else:
            n = g[0]
    if n != s1:
        print('POSSIBLE')
        exit()

    # 2
    n = s2
    for g in G:
        if g[0] == n:
            n = g[1]
        else:
            n = g[0]
    if n == s1:
        print('POSSIBLE')
        exit()

    print('IMPOSSIBLE')

Submission status: Runtime Error

Solution code:
# coding: utf-8
from collections import defaultdict


def II(): return int(input())
def ILI(): return list(map(int, input().split()))


def read():
    N = II()
    p = ILI()
    return N, p


def solve(N, p):
    ans = None
    edges = defaultdict(list)
    for i in range(N):
        edges[p[i]].append(i + 1)

    nodes_has_branch = []
    for i in range(1, N + 1):
        if len(edges[i]) == 2:
            nodes_has_branch.append(i)

    if len(nodes_has_branch) == 0:
        if N % 2 == 0:
            ans = "POSSIBLE"
        else:
            ans = "IMPOSSIBLE"
    else:
        first_node = nodes_has_branch[0]
        edges_reverse = defaultdict(list)
        for fro, to in edges.items():
            for i in to:
                edges_reverse[i].append(fro)
        circles = []
        next_node = edges_reverse[first_node]
        while True:
            if next_node[0] == first_node:
                break
            circles.append(next_node[0])
            next_node = edges_reverse[next_node[0]]

        circles = [first_node] + list(reversed(circles))

        s_circles = set(circles)
        s_branch = set(range(1, N + 1)) - s_circles

        circles_depth = [0] * len(circles)
        for i, node in enumerate(circles):
            next_node = edges[node]
            if len(next_node) == 1:
                continue
            else:
                next_node = list((set(next_node) & s_branch))[0]
                while True:
                    circles_depth[i] += 1
                    next_node = edges[next_node]
                    if len(next_node) == 0:
                        break

        if not 0 in circles_depth:
            ans = "IMPOSSIBLE"
        else:
            ans = "POSSIBLE"

    return ans


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()