(cache)Submission #67144391 - 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 #67144391

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
#include<iostream>
#include<vector>
using namespace std;
int n,m;
vector<vector<bool>>node(9,vector<bool>(9,false));
int f(vector<int>count,int now,int cost){
  if(now==n+1){
    bool ok=true;
    for(int i=0;i<n;i++)if(count[i]!=2)ok=false;
    if(ok)return n-cost+m-cost;
    else return 1e9;
  }
  int ans=1e9;
  if(count[now-1]==2)return f(count,now+1,cost);
  if(count[now-1]==0){
    vector<pair<int,int>>num;
    for(int i=now+1;i<n;i++)for(int j=i+1;j<=n;j++){
  if(count[i-1]==2 || count[j-1]==2)continue;
  count[now-1]+=2;
  count[i-1]++;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include<iostream>
#include<vector>
using namespace std;
int n,m;
vector<vector<bool>>node(9,vector<bool>(9,false));
int f(vector<int>count,int now,int cost){
  if(now==n+1){
    bool ok=true;
    for(int i=0;i<n;i++)if(count[i]!=2)ok=false;
    if(ok)return n-cost+m-cost;
    else return 1e9;
  }
  int ans=1e9;
  if(count[now-1]==2)return f(count,now+1,cost);

  if(count[now-1]==0){
    vector<pair<int,int>>num;
    for(int i=now+1;i<n;i++)for(int j=i+1;j<=n;j++){
	if(count[i-1]==2 || count[j-1]==2)continue;
	count[now-1]+=2;
	count[i-1]++;
	count[j-1]++;
	int hako=0;
	if(node[now][i])hako++;
	if(node[now][j])hako++;
	ans=min(ans,f(count,now+1,cost+hako));
	count[now-1]-=2;
	count[i-1]--;
	count[j-1]--;
      }
  }
  else{
    for(int i=now+1;i<=n;i++){
      if(count[i-1]==2)continue;
      count[now-1]++;
      count[i-1]++;

      int hako=0;
      if(node[now][i])hako++;
      ans=min(ans,f(count,now+1,cost+hako));
      count[now-1]--;
      count[i-1]--;
    }
  }
  return ans;
}   
    
int main()
{
  cin >> n >> m;
  for(int i=0;i<m;i++){
    int a,b;
    cin >> a >> b;
    if(a>b)swap(a,b);
    node[a][b]=true;
    node[b][a]=true;
  }
  vector<int>count(n,0);
  cout << f(count,1,0) << endl;
}

Submission Info

Submission Time	2025-06-28 21:38:39
Task	D - Make 2-Regular Graph
User	rotti
Language	C++ 20 (gcc 12.2)
Score	425
Code Size	1281 Byte
Status	AC
Exec Time	2 ms
Memory	3676 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	1 ms	3488 KiB
sample01.txt	AC	1 ms	3492 KiB
sample02.txt	AC	1 ms	3488 KiB
sample03.txt	AC	1 ms	3484 KiB
testcase00.txt	AC	1 ms	3404 KiB
testcase01.txt	AC	1 ms	3604 KiB
testcase02.txt	AC	1 ms	3516 KiB
testcase03.txt	AC	1 ms	3472 KiB
testcase04.txt	AC	1 ms	3476 KiB
testcase05.txt	AC	1 ms	3476 KiB
testcase06.txt	AC	1 ms	3492 KiB
testcase07.txt	AC	1 ms	3540 KiB
testcase08.txt	AC	1 ms	3476 KiB
testcase09.txt	AC	1 ms	3676 KiB
testcase10.txt	AC	1 ms	3492 KiB
testcase11.txt	AC	1 ms	3444 KiB
testcase12.txt	AC	1 ms	3532 KiB
testcase13.txt	AC	1 ms	3440 KiB
testcase14.txt	AC	1 ms	3488 KiB
testcase15.txt	AC	1 ms	3448 KiB
testcase16.txt	AC	1 ms	3532 KiB
testcase17.txt	AC	1 ms	3540 KiB
testcase18.txt	AC	1 ms	3676 KiB
testcase19.txt	AC	1 ms	3476 KiB
testcase20.txt	AC	1 ms	3536 KiB
testcase21.txt	AC	1 ms	3444 KiB
testcase22.txt	AC	1 ms	3476 KiB
testcase23.txt	AC	1 ms	3536 KiB
testcase24.txt	AC	1 ms	3444 KiB
testcase25.txt	AC	1 ms	3532 KiB
testcase26.txt	AC	1 ms	3672 KiB
testcase27.txt	AC	1 ms	3536 KiB
testcase28.txt	AC	1 ms	3488 KiB
testcase29.txt	AC	1 ms	3448 KiB
testcase30.txt	AC	1 ms	3492 KiB
testcase31.txt	AC	1 ms	3608 KiB
testcase32.txt	AC	2 ms	3468 KiB
testcase33.txt	AC	2 ms	3488 KiB
testcase34.txt	AC	1 ms	3404 KiB
testcase35.txt	AC	1 ms	3400 KiB
testcase36.txt	AC	1 ms	3480 KiB
testcase37.txt	AC	1 ms	3536 KiB
testcase38.txt	AC	1 ms	3476 KiB
testcase39.txt	AC	1 ms	3448 KiB
testcase40.txt	AC	1 ms	3484 KiB
testcase41.txt	AC	1 ms	3608 KiB
testcase42.txt	AC	1 ms	3532 KiB
testcase43.txt	AC	1 ms	3488 KiB
testcase44.txt	AC	1 ms	3536 KiB
testcase45.txt	AC	1 ms	3468 KiB
testcase46.txt	AC	1 ms	3536 KiB
testcase47.txt	AC	1 ms	3472 KiB
testcase48.txt	AC	1 ms	3488 KiB
testcase49.txt	AC	1 ms	3472 KiB
testcase50.txt	AC	1 ms	3480 KiB
testcase51.txt	AC	2 ms	3476 KiB