제출 #914442

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
914442		Isaac_Q1	경주 (Race) (IOI11_race)	C++14	0 / 100	3044 ms	2396 KiB

race

#include<bits/stdc++.h>
#include<vector>
using namespace std;
vector<int> temp;
int res = INT_MAX;
int check(int h[][2])
{
    int ht[100]={0};
    int cnt = 0;
    int n = temp.size();
    for(int i=0; i<n; i++)
    {
        ht[h[i][0]] ++;
        ht[h[i][1]] ++;
        cnt += 2;
        if(ht[h[i][0]] == 2) cnt -= 2;
        else if(ht[h[i][0]] > 2) return 0;
        if(ht[h[i][1]] == 2) cnt -= 2;
        else if(ht[h[i][1]] > 2) return 0;
    }
    if(cnt == 2) return 1;
    return 0;
}
void sub(int a[], int ind, int target, int n,int h[][2])
{
    if(ind >= n) return;
    if(target < 0) return;
    if(target == 0) 
    {
        if(check(h)){
        int k = temp.size();
        res = min(res, k);
        }
        return;
    } 
    for(int i = ind; i<n; i++) 
    {
        temp.push_back(i);
        target -= a[i];
        sub(a,i+1,target,n,h);
        target += a[i];
        temp.pop_back();
    }
    return;
}
int best_path(int N, int K, int H[][2], int L[])
{
    int u;
    int u1,u2;
    for(int i=0; i<N-2; i++)
    {
        for(int j=i+1; j<N-1; j++)
        {
            if(L[i] > L[j])
            {
                u = L[i];
                L[i] = L[j];
                L[j] = u;
 
                u1 = H[i][0];
                H[i][0] = H[j][0];
                H[j][0] = u1;
 
                u2 = H[i][1];
                H[i][1] = H[j][1];
                H[j][1] = u2;
            }
        }
    }
    sub(L,0,K,N-1,H);
    if(res == INT_MAX) return -1;
    return res;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57