Submission #1051062

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1051062	2024-08-09T19:06:55 Z	ivopav	Marriage questions (IZhO14_marriage)	C++17	38 / 100	1500 ms	5828 KB

marriage

#include <bits/stdc++.h>
using namespace std;

struct edg{
    int ind;
    int val;
    int inv;
};

bool dfs(int ind,vector<vector<edg>>& gra,vector<bool>& bio){
    //cout << ind << "\n";
    if (ind==gra.size()-1){
        return 1;
    }
    for (int i=0;i<gra[ind].size();i++){
        int ind2=gra[ind][i].ind;
        if (bio[ind2]==1 || gra[ind][i].val==0){
            continue;
        }
        bio[ind2]=1;
        //gra[ind2][gra[ind][i].inv].val=1;
        gra[ind][i].val=0;
        if (dfs(ind2,gra,bio)){
            return 1;
        }
        bio[ind2]=0;
        //gra[ind2][gra[ind][i].inv].val=0;
        gra[ind][i].val=1;
    }
    //cout << "aa\n";
    return 0;   
}

bool mog(int n,int m,int l,int r,vector<vector<int>>& gra){
    //cout << "a\n";
    vector<vector<edg>> gra2(n+m+2,vector<edg>{});
    for (int i=0;i<n;i++){
        for (int j=0;j<gra[i].size();j++){
            int ind=gra[i][j];
            if (ind-n>=l && ind-n<=r){
                gra2[i].push_back({ind,1,gra2[ind].size()});
                gra2[ind].push_back({i,0,gra2[i].size()-1});
            }
        }
    }
    for (int i=0;i<n;i++){
        gra2[i].push_back({n+m,0,gra2[n+m].size()});
        gra2[n+m].push_back({i,1,gra2[i].size()-1});
        
    }
    for (int i=n+l;i<=n+r;i++){
        gra2[i].push_back({n+m+1,1,gra2[n+m+1].size()});
        gra2[n+m+1].push_back({i,0,gra2[i].size()-1});
        
    }
    int kol=0;
    while (true){
        //cout << kol << "\n";
        vector<bool> bio(n+m+2,0);
        if (!dfs(n+m,gra2,bio)){
            break;
        }
        kol++;
    }
    //cout << "b\n";
    //cout << kol << " " << n << " " << l << " " << r << "\n"; 
    if (kol>=n){
        return 1;
    }
    else {
        return 0;
    }

    
}

int main(){
    int n;
    int m;
    int k;
    cin >> m >> n >> k;
    vector<vector<int>> gra(n+m,vector<int>{});
    for (int i=0;i<k;i++){
        int unos;
        int unos2;
        cin >> unos >> unos2;
        gra[--unos+n].push_back(--unos2);
        gra[unos2].push_back(unos+n);
        

    }    
    int l=0;
    int r=0;
    int rje=0;
    for (int l=0;l<m;l++){
        while (r<m){
            bool dob=mog(n,m,l,r,gra);
            if (dob){
                break;
            }
            r++;
        }
        rje+=m-r;
        if (r<l){
            r++;
        }
    }
    cout << rje << "\n";
}

Compilation message

marriage.cpp: In function 'bool dfs(int, std::vector<std::vector<edg> >&, std::vector<bool>&)':
marriage.cpp:12:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<edg> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     if (ind==gra.size()-1){
      |         ~~~^~~~~~~~~~~~~~
marriage.cpp:15:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for (int i=0;i<gra[ind].size();i++){
      |                  ~^~~~~~~~~~~~~~~~
marriage.cpp: In function 'bool mog(int, int, int, int, std::vector<std::vector<int> >&)':
marriage.cpp:38:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         for (int j=0;j<gra[i].size();j++){
      |                      ~^~~~~~~~~~~~~~
marriage.cpp:41:56: warning: narrowing conversion of '(& gra2.std::vector<std::vector<edg> >::operator[](((std::vector<std::vector<edg> >::size_type)ind)))->std::vector<edg>::size()' from 'std::vector<edg>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   41 |                 gra2[i].push_back({ind,1,gra2[ind].size()});
      |                                          ~~~~~~~~~~~~~~^~
marriage.cpp:42:56: warning: narrowing conversion of '((& gra2.std::vector<std::vector<edg> >::operator[](((std::vector<std::vector<edg> >::size_type)i)))->std::vector<edg>::size() - 1)' from 'std::vector<edg>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   42 |                 gra2[ind].push_back({i,0,gra2[i].size()-1});
      |                                          ~~~~~~~~~~~~~~^~
marriage.cpp:47:48: warning: narrowing conversion of '(& gra2.std::vector<std::vector<edg> >::operator[](((std::vector<std::vector<edg> >::size_type)(n + m))))->std::vector<edg>::size()' from 'std::vector<edg>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   47 |         gra2[i].push_back({n+m,0,gra2[n+m].size()});
      |                                  ~~~~~~~~~~~~~~^~
marriage.cpp:48:48: warning: narrowing conversion of '((& gra2.std::vector<std::vector<edg> >::operator[](((std::vector<std::vector<edg> >::size_type)i)))->std::vector<edg>::size() - 1)' from 'std::vector<edg>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   48 |         gra2[n+m].push_back({i,1,gra2[i].size()-1});
      |                                  ~~~~~~~~~~~~~~^~
marriage.cpp:52:52: warning: narrowing conversion of '(& gra2.std::vector<std::vector<edg> >::operator[](((std::vector<std::vector<edg> >::size_type)((n + m) + 1))))->std::vector<edg>::size()' from 'std::vector<edg>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   52 |         gra2[i].push_back({n+m+1,1,gra2[n+m+1].size()});
      |                                    ~~~~~~~~~~~~~~~~^~
marriage.cpp:53:50: warning: narrowing conversion of '((& gra2.std::vector<std::vector<edg> >::operator[](((std::vector<std::vector<edg> >::size_type)i)))->std::vector<edg>::size() - 1)' from 'std::vector<edg>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   53 |         gra2[n+m+1].push_back({i,0,gra2[i].size()-1});
      |                                    ~~~~~~~~~~~~~~^~
marriage.cpp: In function 'int main()':
marriage.cpp:92:9: warning: unused variable 'l' [-Wunused-variable]
   92 |     int l=0;
      |         ^

Subtask #1

38.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Incorrect	0 ms	348 KB	Output isn't correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Incorrect	0 ms	348 KB	Output isn't correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Incorrect	0 ms	348 KB	Output isn't correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Incorrect	0 ms	348 KB	Output isn't correct
15	Incorrect	0 ms	436 KB	Output isn't correct
16	Incorrect	0 ms	348 KB	Output isn't correct
17	Correct	0 ms	440 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Incorrect	9 ms	348 KB	Output isn't correct
20	Incorrect	2 ms	440 KB	Output isn't correct
21	Correct	1 ms	348 KB	Output is correct
22	Incorrect	1 ms	348 KB	Output isn't correct
23	Correct	7 ms	436 KB	Output is correct
24	Correct	3 ms	348 KB	Output is correct
25	Incorrect	121 ms	816 KB	Output isn't correct
26	Incorrect	74 ms	552 KB	Output isn't correct
27	Correct	18 ms	504 KB	Output is correct
28	Incorrect	13 ms	348 KB	Output isn't correct
29	Correct	84 ms	924 KB	Output is correct
30	Correct	68 ms	916 KB	Output is correct
31	Execution timed out	1530 ms	2552 KB	Time limit exceeded
32	Incorrect	487 ms	848 KB	Output isn't correct
33	Correct	242 ms	732 KB	Output is correct
34	Incorrect	145 ms	592 KB	Output isn't correct
35	Execution timed out	1575 ms	5360 KB	Time limit exceeded
36	Execution timed out	1564 ms	4968 KB	Time limit exceeded
37	Execution timed out	1567 ms	2264 KB	Time limit exceeded
38	Execution timed out	1529 ms	5828 KB	Time limit exceeded
39	Execution timed out	1524 ms	1512 KB	Time limit exceeded
40	Execution timed out	1570 ms	1472 KB	Time limit exceeded
41	Execution timed out	1559 ms	1724 KB	Time limit exceeded
42	Execution timed out	1575 ms	2516 KB	Time limit exceeded
43	Execution timed out	1537 ms	3036 KB	Time limit exceeded
44	Execution timed out	1564 ms	4032 KB	Time limit exceeded
45	Execution timed out	1560 ms	3156 KB	Time limit exceeded
46	Execution timed out	1540 ms	4476 KB	Time limit exceeded
47	Execution timed out	1532 ms	4808 KB	Time limit exceeded
48	Execution timed out	1538 ms	4696 KB	Time limit exceeded
49	Execution timed out	1574 ms	4660 KB	Time limit exceeded
50	Execution timed out	1565 ms	2272 KB	Time limit exceeded