(cache)Submission #67148527 - AtCoder Beginner Contest 412

Contest Duration: 2025-06-28(Sat) 21:00 - 2025-06-28(Sat) 22:40 (local time) (100 minutes) Back to Home

Submission #67148527

Source Code Expand

Copy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from itertools import combinations, permutations
N,M=map(int, input().split())
edge={tuple(sorted(map(int,input().split()))) for _ in range(M)}
ans=float('inf')
def dfs(rem,crr):
    global ans
    if not rem:
        diff1=edge-crr
        diff2=crr-edge
        ops=len(diff1 | diff2)
        ans=min(ans,ops)
        return
    u=min(rem)
    rem.discard(u)
    ver=list(rem)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

from itertools import combinations, permutations


N,M=map(int, input().split())
edge={tuple(sorted(map(int,input().split()))) for _ in range(M)}

ans=float('inf')

def dfs(rem,crr):
    global ans
    if not rem:
        diff1=edge-crr
        diff2=crr-edge
        ops=len(diff1 | diff2)
        ans=min(ans,ops)
        return


    u=min(rem)
    rem.discard(u)
    ver=list(rem)

    for k in range(3, len(ver)+2):
        for comb in combinations(ver,k-1):
            cycle=[u]+list(comb)

            for perm in permutations(cycle[1:]):
                cyc=[u]+list(perm)
                nxt=set(crr)
                for i in range(len(cyc)):
                    a,b=sorted((cyc[i],cyc[(i+1)%len(cyc)]))
                    nxt.add((a,b))

                nxt_r=rem-set(comb)
                dfs(nxt_r,nxt)
    rem.add(u)

dfs(set(range(1,N+1)), set())
print(ans)

Submission Info

Submission Time	2025-06-28 21:49:41
Task	D - Make 2-Regular Graph
User	kotafuku
Language	Python (PyPy 3.10-v7.3.12)
Score	425
Code Size	917 Byte
Status	AC
Exec Time	142 ms
Memory	84252 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

425 / 425

Status

× 4

× 56

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	56 ms	76468 KiB
sample01.txt	AC	55 ms	76720 KiB
sample02.txt	AC	63 ms	81912 KiB
sample03.txt	AC	135 ms	84036 KiB
testcase00.txt	AC	56 ms	76896 KiB
testcase01.txt	AC	56 ms	76684 KiB
testcase02.txt	AC	56 ms	76776 KiB
testcase03.txt	AC	57 ms	76860 KiB
testcase04.txt	AC	120 ms	84176 KiB
testcase05.txt	AC	58 ms	76636 KiB
testcase06.txt	AC	82 ms	83528 KiB
testcase07.txt	AC	141 ms	83916 KiB
testcase08.txt	AC	58 ms	76652 KiB
testcase09.txt	AC	63 ms	81840 KiB
testcase10.txt	AC	130 ms	83644 KiB
testcase11.txt	AC	58 ms	76476 KiB
testcase12.txt	AC	57 ms	76640 KiB
testcase13.txt	AC	64 ms	81896 KiB
testcase14.txt	AC	84 ms	83208 KiB
testcase15.txt	AC	129 ms	83932 KiB
testcase16.txt	AC	130 ms	83992 KiB
testcase17.txt	AC	64 ms	81588 KiB
testcase18.txt	AC	84 ms	83296 KiB
testcase19.txt	AC	130 ms	84104 KiB
testcase20.txt	AC	130 ms	84124 KiB
testcase21.txt	AC	64 ms	81512 KiB
testcase22.txt	AC	65 ms	81844 KiB
testcase23.txt	AC	84 ms	83516 KiB
testcase24.txt	AC	81 ms	83232 KiB
testcase25.txt	AC	126 ms	83920 KiB
testcase26.txt	AC	127 ms	83760 KiB
testcase27.txt	AC	127 ms	83896 KiB
testcase28.txt	AC	127 ms	83684 KiB
testcase29.txt	AC	81 ms	83128 KiB
testcase30.txt	AC	128 ms	84020 KiB
testcase31.txt	AC	64 ms	81808 KiB
testcase32.txt	AC	127 ms	83884 KiB
testcase33.txt	AC	129 ms	83876 KiB
testcase34.txt	AC	127 ms	84252 KiB
testcase35.txt	AC	126 ms	83980 KiB
testcase36.txt	AC	56 ms	76296 KiB
testcase37.txt	AC	125 ms	84112 KiB
testcase38.txt	AC	81 ms	83256 KiB
testcase39.txt	AC	126 ms	84192 KiB
testcase40.txt	AC	55 ms	76412 KiB
testcase41.txt	AC	130 ms	83728 KiB
testcase42.txt	AC	56 ms	76460 KiB
testcase43.txt	AC	133 ms	84024 KiB
testcase44.txt	AC	56 ms	76908 KiB
testcase45.txt	AC	129 ms	83972 KiB
testcase46.txt	AC	84 ms	83140 KiB
testcase47.txt	AC	132 ms	83688 KiB
testcase48.txt	AC	57 ms	76416 KiB
testcase49.txt	AC	138 ms	84232 KiB
testcase50.txt	AC	62 ms	81508 KiB
testcase51.txt	AC	142 ms	83892 KiB