Submission #67154519

Source Code Expand

Copy
# Modules ここからコピペ
# https://github.com/kangping-git/AtCoder-Module/tree/main
def calcScore(perm,graph_new):
    N = len(perm)
    vertex = set(perm)
    score = 0
    for i in range(N):
        for j in graph[perm[i]]:
            if j not in vertex:
                continue
            if not (j == perm[(i-1) % N] or j == perm[(i+1) % N]) and (j in graph_new[perm[i]] and perm[i] in  graph_new[j]):
                graph_new[perm[i]].discard(j)
                graph_new[j].discard(perm[i])
                score += 1
        if not (perm[(i-1) % N] in graph_new[perm[i]]):
            graph_new[perm[i]].add(perm[(i-1) % N])
            graph_new[perm[(i-1) % N]].add(perm[i])
            score += 1
        if not (perm[(i+1) % N] in graph_new[perm[i]]):
            graph_new[perm[i]].add(perm[(i+1) % N])
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
# Modules ここからコピペ
# https://github.com/kangping-git/AtCoder-Module/tree/main

def calcScore(perm,graph_new):
    N = len(perm)
    vertex = set(perm)
    score = 0
    for i in range(N):
        for j in graph[perm[i]]:
            if j not in vertex:
                continue
            if not (j == perm[(i-1) % N] or j == perm[(i+1) % N]) and (j in graph_new[perm[i]] and perm[i] in  graph_new[j]):
                graph_new[perm[i]].discard(j)
                graph_new[j].discard(perm[i])
                score += 1
        if not (perm[(i-1) % N] in graph_new[perm[i]]):
            graph_new[perm[i]].add(perm[(i-1) % N])
            graph_new[perm[(i-1) % N]].add(perm[i])
            score += 1
        if not (perm[(i+1) % N] in graph_new[perm[i]]):
            graph_new[perm[i]].add(perm[(i+1) % N])
            graph_new[perm[(i+1) % N]].add(perm[i])
            score += 1
    return score

import itertools
import copy

N,M = map(int, input().split())

graph = {}
for _ in range(1, N+1):
    graph[_] = set()
for _ in range(M):
    a, b = map(int, input().split())
    graph[a].add(b)
    graph[b].add(a)

min_score = float('inf')
for perm in itertools.permutations(range(1, N+1)):
    graph_new = copy.deepcopy(graph)
    score = calcScore(perm,graph_new)
    min_score = min(min_score, score)
    if N >= 6:
        for i in range(3, N-2):
            graph_new = copy.deepcopy(graph)
            anotherScore = calcScore(perm[:i],graph_new)
            anotherScore += calcScore(perm[i:],graph_new)
            edge_count = 0
            for j in graph_new:
                edge_count += len(graph_new[j])
            edge_count //= 2
            anotherScore += edge_count - N

            min_score = min(min_score, anotherScore)
print(min_score)

Submission Info

Submission Time
Task D - Make 2-Regular Graph
User kangping
Language Python (PyPy 3.10-v7.3.12)
Score 0
Code Size 1836 Byte
Status TLE
Exec Time 2213 ms
Memory 120232 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 425
Status
AC × 3
TLE × 1
AC × 52
TLE × 4
Set Name Test Cases
Sample sample00.txt, sample01.txt, sample02.txt, sample03.txt
All sample00.txt, sample01.txt, sample02.txt, sample03.txt, testcase00.txt, testcase01.txt, testcase02.txt, testcase03.txt, testcase04.txt, testcase05.txt, testcase06.txt, testcase07.txt, testcase08.txt, testcase09.txt, testcase10.txt, testcase11.txt, testcase12.txt, testcase13.txt, testcase14.txt, testcase15.txt, testcase16.txt, testcase17.txt, testcase18.txt, testcase19.txt, testcase20.txt, testcase21.txt, testcase22.txt, testcase23.txt, testcase24.txt, testcase25.txt, testcase26.txt, testcase27.txt, testcase28.txt, testcase29.txt, testcase30.txt, testcase31.txt, testcase32.txt, testcase33.txt, testcase34.txt, testcase35.txt, testcase36.txt, testcase37.txt, testcase38.txt, testcase39.txt, testcase40.txt, testcase41.txt, testcase42.txt, testcase43.txt, testcase44.txt, testcase45.txt, testcase46.txt, testcase47.txt, testcase48.txt, testcase49.txt, testcase50.txt, testcase51.txt
Case Name Status Exec Time Memory
sample00.txt AC 85 ms 83864 KiB
sample01.txt AC 66 ms 76964 KiB
sample02.txt AC 157 ms 86440 KiB
sample03.txt TLE 2047 ms 116064 KiB
testcase00.txt AC 64 ms 76980 KiB
testcase01.txt AC 64 ms 77180 KiB
testcase02.txt AC 64 ms 76768 KiB
testcase03.txt AC 83 ms 84640 KiB
testcase04.txt AC 862 ms 92304 KiB
testcase05.txt AC 66 ms 76800 KiB
testcase06.txt AC 348 ms 89716 KiB
testcase07.txt TLE 2213 ms 114944 KiB
testcase08.txt AC 86 ms 83832 KiB
testcase09.txt AC 154 ms 88016 KiB
testcase10.txt AC 1606 ms 114704 KiB
testcase11.txt AC 66 ms 77012 KiB
testcase12.txt AC 85 ms 83888 KiB
testcase13.txt AC 148 ms 87948 KiB
testcase14.txt AC 327 ms 90532 KiB
testcase15.txt AC 1667 ms 117440 KiB
testcase16.txt AC 1637 ms 115572 KiB
testcase17.txt AC 152 ms 88552 KiB
testcase18.txt AC 316 ms 90912 KiB
testcase19.txt AC 1568 ms 116860 KiB
testcase20.txt AC 1614 ms 116644 KiB
testcase21.txt AC 159 ms 87592 KiB
testcase22.txt AC 159 ms 87524 KiB
testcase23.txt AC 327 ms 90400 KiB
testcase24.txt AC 336 ms 91776 KiB
testcase25.txt AC 1653 ms 116712 KiB
testcase26.txt AC 1698 ms 116800 KiB
testcase27.txt AC 1643 ms 119508 KiB
testcase28.txt AC 1848 ms 120232 KiB
testcase29.txt AC 329 ms 90976 KiB
testcase30.txt AC 1727 ms 117204 KiB
testcase31.txt AC 170 ms 86356 KiB
testcase32.txt AC 1677 ms 117412 KiB
testcase33.txt AC 1616 ms 117204 KiB
testcase34.txt AC 1730 ms 118000 KiB
testcase35.txt AC 1711 ms 119508 KiB
testcase36.txt AC 67 ms 77244 KiB
testcase37.txt AC 1674 ms 118016 KiB
testcase38.txt AC 380 ms 90484 KiB
testcase39.txt AC 1773 ms 118120 KiB
testcase40.txt AC 66 ms 76884 KiB
testcase41.txt AC 1833 ms 116032 KiB
testcase42.txt AC 85 ms 84024 KiB
testcase43.txt AC 1912 ms 116788 KiB
testcase44.txt AC 67 ms 76812 KiB
testcase45.txt AC 1888 ms 117172 KiB
testcase46.txt AC 348 ms 92600 KiB
testcase47.txt AC 1809 ms 118580 KiB
testcase48.txt AC 67 ms 76856 KiB
testcase49.txt TLE 2101 ms 116588 KiB
testcase50.txt AC 149 ms 86524 KiB
testcase51.txt TLE 2213 ms 116480 KiB
Facebook Twitter Telegram Share

2025-07-09 (Wed)
03:04:36 +09:00

More…