제출 #343953

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
343953		kkk	결혼 문제 (IZhO14_marriage)	C++14	12 / 100	1599 ms	9196 KiB

marriage

#include<iostream>
#include<cstring>
#include<vector>
#define endl '\n'
using namespace std;
vector <long long> v[300000];
bool used[3000];
long long br=0,le=0,m,bru=0;
long long rec(long long pr,long long fi,long long bru)
{

    if(pr>fi)return 0;
    long long rez=0;
    for(int i=0;i<v[pr].size();i++)
    {
        if(!used[v[pr][i]])
        {
        if(pr==fi && bru==m-1)return 1;
            used[v[pr][i]]=1;
            rez+=rec(pr+1,fi,bru+1);
            used[v[pr][i]]=0;
        }


    } rez+=rec(pr+1,fi,bru);
    return rez;

}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    long long n,k,i,a,b,p,j,brr=0,le,ri,mid;
    cin>>n>>m>>k;

    for(i=0;i<k;i++)
    {
        cin>>a>>b;
        v[a].push_back(b);
        le=a;
    }

    for(i=1;i<=n;i++)
    {

        //for(j=i;j<=n;j++){
                //cout<<i<<" "<<j<<" "<<rec(i,j,0)<<endl;
        le=i-1;ri=n+1;
        while(le<=ri)
        {   //cout<<le<<" "<<ri<<" "<<mid<<endl;
            mid=(le+ri)/2;
            if(rec(i,mid,0)>0)ri=mid-1;
            else le=mid+1;
            memset(used,0,sizeof(used));
        }
    // cout<<n-mid<<endl;;
       brr+=n-mid;
        if(n-mid<0)brr-=n-mid;
        }

    cout<<brr<<endl;
}

컴파일 시 표준 에러 (stderr) 메시지

marriage.cpp: In function 'long long int rec(long long int, long long int, long long int)':
marriage.cpp:14:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for(int i=0;i<v[pr].size();i++)
      |                 ~^~~~~~~~~~~~~
marriage.cpp: In function 'int main()':
marriage.cpp:35:25: warning: unused variable 'p' [-Wunused-variable]
   35 |     long long n,k,i,a,b,p,j,brr=0,le,ri,mid;
      |                         ^
marriage.cpp:35:27: warning: unused variable 'j' [-Wunused-variable]
   35 |     long long n,k,i,a,b,p,j,brr=0,le,ri,mid;
      |                           ^
marriage.cpp:59:14: warning: 'mid' may be used uninitialized in this function [-Wmaybe-uninitialized]
   59 |        brr+=n-mid;
      |             ~^~~~

• Subtask 1: 12 / 100