Submission #1051067

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1051067	2024-08-09T19:10:30 Z	ivopav	Marriage questions (IZhO14_marriage)	C++17	48 / 100	1500 ms	4216 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

48.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	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	3 ms	348 KB	Output is 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	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Execution timed out	1597 ms	348 KB	Time limit exceeded
20	Execution timed out	1560 ms	348 KB	Time limit exceeded
21	Correct	5 ms	344 KB	Output is correct
22	Correct	5 ms	348 KB	Output is correct
23	Execution timed out	1564 ms	348 KB	Time limit exceeded
24	Execution timed out	1554 ms	348 KB	Time limit exceeded
25	Execution timed out	1581 ms	600 KB	Time limit exceeded
26	Execution timed out	1505 ms	344 KB	Time limit exceeded
27	Correct	28 ms	344 KB	Output is correct
28	Correct	83 ms	480 KB	Output is correct
29	Correct	127 ms	852 KB	Output is correct
30	Correct	88 ms	852 KB	Output is correct
31	Execution timed out	1580 ms	860 KB	Time limit exceeded
32	Execution timed out	1568 ms	604 KB	Time limit exceeded
33	Execution timed out	1529 ms	564 KB	Time limit exceeded
34	Execution timed out	1549 ms	548 KB	Time limit exceeded
35	Execution timed out	1535 ms	4216 KB	Time limit exceeded
36	Execution timed out	1548 ms	4200 KB	Time limit exceeded
37	Execution timed out	1569 ms	1116 KB	Time limit exceeded
38	Execution timed out	1563 ms	2372 KB	Time limit exceeded
39	Execution timed out	1545 ms	1116 KB	Time limit exceeded
40	Execution timed out	1543 ms	1368 KB	Time limit exceeded
41	Execution timed out	1532 ms	1484 KB	Time limit exceeded
42	Execution timed out	1551 ms	1764 KB	Time limit exceeded
43	Execution timed out	1540 ms	1928 KB	Time limit exceeded
44	Execution timed out	1566 ms	2396 KB	Time limit exceeded
45	Execution timed out	1558 ms	2652 KB	Time limit exceeded
46	Execution timed out	1560 ms	3428 KB	Time limit exceeded
47	Execution timed out	1539 ms	3424 KB	Time limit exceeded
48	Execution timed out	1556 ms	3440 KB	Time limit exceeded
49	Execution timed out	1597 ms	3424 KB	Time limit exceeded
50	Execution timed out	1536 ms	2144 KB	Time limit exceeded