Submission #1051065

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

marriage

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

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

bool dfs(long long int ind,vector<vector<edg>>& gra,vector<bool>& bio){
    //cout << ind << "\n";
    if (ind==gra.size()-1){
        return 1;
    }
    for (long long int i=0;i<gra[ind].size();i++){
        long long 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(long long int n,long long int m,long long int l,long long int r,vector<vector<long long int>>& gra){
    //cout << "a\n";
    vector<vector<edg>> gra2(n+m+2,vector<edg>{});
    for (long long int i=0;i<n;i++){
        for (long long int j=0;j<gra[i].size();j++){
            long long 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 (long long 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 (long long 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});
        
    }
    long long 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(){
    long long int n;
    long long int m;
    long long int k;
    cin >> m >> n >> k;
    vector<vector<long long int>> gra(n+m,vector<long long int>{});
    for (long long int i=0;i<k;i++){
        long long int unos;
        long long int unos2;
        cin >> unos >> unos2;
        gra[--unos+n].push_back(--unos2);
        gra[unos2].push_back(unos+n);
        

    }    
    long long int l=0;
    long long int r=0;
    long long int rje=0;
    for (long long 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(long long int, std::vector<std::vector<edg> >&, std::vector<bool>&)':
marriage.cpp:12:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<edg> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     if (ind==gra.size()-1){
      |         ~~~^~~~~~~~~~~~~~
marriage.cpp:15:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<edg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for (long long int i=0;i<gra[ind].size();i++){
      |                            ~^~~~~~~~~~~~~~~~
marriage.cpp: In function 'bool mog(long long int, long long int, long long int, long long int, std::vector<std::vector<long long int> >&)':
marriage.cpp:38:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         for (long long 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 'long long 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 'long long 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 'long long 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 'long long 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 'long long 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 'long long int' [-Wnarrowing]
   53 |         gra2[n+m+1].push_back({i,0,gra2[i].size()-1});
      |                                    ~~~~~~~~~~~~~~^~
marriage.cpp: In function 'int main()':
marriage.cpp:92:19: warning: unused variable 'l' [-Wunused-variable]
   92 |     long long int l=0;
      |                   ^

Subtask #1

38.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 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	0 ms	348 KB	Output is correct
14	Incorrect	0 ms	348 KB	Output isn't correct
15	Incorrect	0 ms	348 KB	Output isn't correct
16	Incorrect	0 ms	348 KB	Output isn't correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Incorrect	8 ms	592 KB	Output isn't correct
20	Incorrect	3 ms	344 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	4 ms	348 KB	Output is correct
24	Correct	4 ms	348 KB	Output is correct
25	Incorrect	121 ms	996 KB	Output isn't correct
26	Incorrect	51 ms	616 KB	Output isn't correct
27	Correct	19 ms	344 KB	Output is correct
28	Incorrect	12 ms	480 KB	Output isn't correct
29	Correct	83 ms	1280 KB	Output is correct
30	Correct	71 ms	1228 KB	Output is correct
31	Execution timed out	1524 ms	3952 KB	Time limit exceeded
32	Incorrect	510 ms	956 KB	Output isn't correct
33	Correct	240 ms	592 KB	Output is correct
34	Incorrect	150 ms	700 KB	Output isn't correct
35	Execution timed out	1543 ms	8496 KB	Time limit exceeded
36	Execution timed out	1504 ms	8132 KB	Time limit exceeded
37	Execution timed out	1594 ms	2944 KB	Time limit exceeded
38	Execution timed out	1527 ms	8556 KB	Time limit exceeded
39	Execution timed out	1554 ms	1588 KB	Time limit exceeded
40	Execution timed out	1556 ms	1500 KB	Time limit exceeded
41	Execution timed out	1533 ms	1740 KB	Time limit exceeded
42	Execution timed out	1546 ms	3000 KB	Time limit exceeded
43	Execution timed out	1538 ms	3720 KB	Time limit exceeded
44	Execution timed out	1573 ms	4548 KB	Time limit exceeded
45	Execution timed out	1513 ms	3172 KB	Time limit exceeded
46	Execution timed out	1546 ms	4612 KB	Time limit exceeded
47	Execution timed out	1530 ms	5212 KB	Time limit exceeded
48	Execution timed out	1528 ms	5216 KB	Time limit exceeded
49	Execution timed out	1570 ms	4712 KB	Time limit exceeded
50	Execution timed out	1533 ms	2400 KB	Time limit exceeded