oj.uz

Submission #343953

# Submission time Handle Problem Language Result Execution time Memory
343953 2021-01-04T21:58:20 Z kkk Marriage questions (IZhO14_marriage) C++14
12 / 100
 1500 ms 9196 KB 
#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;
}

Compilation message

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 7404 KB Output isn't correct
2 Incorrect 5 ms 7404 KB Output isn't correct
3 Incorrect 5 ms 7404 KB Output isn't correct
4 Incorrect 5 ms 7404 KB Output isn't correct
5 Correct 5 ms 7404 KB Output is correct
6 Correct 6 ms 7404 KB Output is correct
7 Execution timed out 1580 ms 7404 KB Time limit exceeded
8 Correct 6 ms 7404 KB Output is correct
9 Correct 5 ms 7404 KB Output is correct
10 Correct 5 ms 7404 KB Output is correct
11 Incorrect 5 ms 7404 KB Output isn't correct
12 Correct 5 ms 7424 KB Output is correct
13 Incorrect 5 ms 7404 KB Output isn't correct
14 Incorrect 367 ms 7404 KB Output isn't correct
15 Incorrect 71 ms 7404 KB Output isn't correct
16 Incorrect 12 ms 7404 KB Output isn't correct
17 Incorrect 95 ms 7404 KB Output isn't correct
18 Incorrect 18 ms 7404 KB Output isn't correct
19 Execution timed out 1583 ms 7404 KB Time limit exceeded
20 Execution timed out 1586 ms 7404 KB Time limit exceeded
21 Execution timed out 1538 ms 7404 KB Time limit exceeded
22 Execution timed out 1590 ms 7404 KB Time limit exceeded
23 Execution timed out 1573 ms 7404 KB Time limit exceeded
24 Execution timed out 1589 ms 7404 KB Time limit exceeded
25 Execution timed out 1596 ms 7532 KB Time limit exceeded
26 Execution timed out 1557 ms 7404 KB Time limit exceeded
27 Execution timed out 1598 ms 7404 KB Time limit exceeded
28 Execution timed out 1592 ms 7404 KB Time limit exceeded
29 Execution timed out 1548 ms 7660 KB Time limit exceeded
30 Execution timed out 1598 ms 7532 KB Time limit exceeded
31 Execution timed out 1599 ms 8044 KB Time limit exceeded
32 Execution timed out 1593 ms 7532 KB Time limit exceeded
33 Execution timed out 1584 ms 7404 KB Time limit exceeded
34 Execution timed out 1586 ms 7404 KB Time limit exceeded
35 Execution timed out 1591 ms 8556 KB Time limit exceeded
36 Execution timed out 1594 ms 8428 KB Time limit exceeded
37 Execution timed out 1588 ms 8172 KB Time limit exceeded
38 Execution timed out 1564 ms 8940 KB Time limit exceeded
39 Execution timed out 1558 ms 7532 KB Time limit exceeded
40 Execution timed out 1545 ms 7808 KB Time limit exceeded
41 Execution timed out 1587 ms 7916 KB Time limit exceeded
42 Execution timed out 1594 ms 7936 KB Time limit exceeded
43 Execution timed out 1595 ms 8044 KB Time limit exceeded
44 Execution timed out 1594 ms 8556 KB Time limit exceeded
45 Execution timed out 1588 ms 8172 KB Time limit exceeded
46 Execution timed out 1585 ms 9068 KB Time limit exceeded
47 Execution timed out 1588 ms 8812 KB Time limit exceeded
48 Execution timed out 1582 ms 8812 KB Time limit exceeded
49 Execution timed out 1591 ms 9196 KB Time limit exceeded
50 Execution timed out 1546 ms 7532 KB Time limit exceeded