oj.uz

Submission #343950

# Submission time Handle Problem Language Result Execution time Memory
343950 2021-01-04T21:35:38 Z kkk Marriage questions (IZhO14_marriage) C++14
36 / 100
 1500 ms 9324 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;
    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;
       if(rec(i,j,0)>0){brr+=n-j+1;break;}
        memset(used,0,sizeof(used));
        }
    }
    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;
      |                         ^

Subtask #1
36.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7404 KB Output is correct
2 Correct 5 ms 7404 KB Output is correct
3 Correct 5 ms 7404 KB Output is correct
4 Correct 5 ms 7404 KB Output is correct
5 Correct 5 ms 7404 KB Output is correct
6 Correct 5 ms 7404 KB Output is correct
7 Correct 329 ms 7532 KB Output is correct
8 Correct 5 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 Correct 5 ms 7404 KB Output is correct
12 Correct 5 ms 7404 KB Output is correct
13 Correct 5 ms 7404 KB Output is correct
14 Correct 94 ms 7444 KB Output is correct
15 Correct 17 ms 7532 KB Output is correct
16 Correct 8 ms 7404 KB Output is correct
17 Correct 38 ms 7404 KB Output is correct
18 Correct 15 ms 7404 KB Output is correct
19 Execution timed out 1589 ms 7404 KB Time limit exceeded
20 Execution timed out 1592 ms 7404 KB Time limit exceeded
21 Execution timed out 1587 ms 7404 KB Time limit exceeded
22 Execution timed out 1596 ms 7404 KB Time limit exceeded
23 Execution timed out 1598 ms 7404 KB Time limit exceeded
24 Execution timed out 1592 ms 7404 KB Time limit exceeded
25 Execution timed out 1592 ms 7660 KB Time limit exceeded
26 Execution timed out 1594 ms 7404 KB Time limit exceeded
27 Execution timed out 1580 ms 7404 KB Time limit exceeded
28 Execution timed out 1590 ms 7404 KB Time limit exceeded
29 Execution timed out 1578 ms 7532 KB Time limit exceeded
30 Execution timed out 1581 ms 7532 KB Time limit exceeded
31 Execution timed out 1586 ms 8300 KB Time limit exceeded
32 Execution timed out 1590 ms 7532 KB Time limit exceeded
33 Execution timed out 1549 ms 7404 KB Time limit exceeded
34 Execution timed out 1584 ms 7404 KB Time limit exceeded
35 Execution timed out 1590 ms 8812 KB Time limit exceeded
36 Execution timed out 1590 ms 8684 KB Time limit exceeded
37 Execution timed out 1588 ms 8428 KB Time limit exceeded
38 Execution timed out 1583 ms 9196 KB Time limit exceeded
39 Execution timed out 1588 ms 7532 KB Time limit exceeded
40 Execution timed out 1592 ms 7660 KB Time limit exceeded
41 Execution timed out 1584 ms 7916 KB Time limit exceeded
42 Execution timed out 1588 ms 8172 KB Time limit exceeded
43 Execution timed out 1595 ms 8300 KB Time limit exceeded
44 Execution timed out 1596 ms 8684 KB Time limit exceeded
45 Execution timed out 1556 ms 8300 KB Time limit exceeded
46 Execution timed out 1589 ms 9196 KB Time limit exceeded
47 Execution timed out 1589 ms 8940 KB Time limit exceeded
48 Execution timed out 1569 ms 9068 KB Time limit exceeded
49 Execution timed out 1587 ms 9324 KB Time limit exceeded
50 Execution timed out 1584 ms 7532 KB Time limit exceeded