Submission #1051067

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051067		ivopav	Marriage questions (IZhO14_marriage)	C++17	48 / 100	1597 ms	4216 KiB

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 (stderr)

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 / 100