oj.uz

Submission #1026090

# Submission time Handle Problem Language Result Execution time Memory
1026090 2024-07-17T14:31:59 Z vjudge1 Marriage questions (IZhO14_marriage) C++17
72 / 100
 1500 ms 262144 KB 
#include "bits/stdc++.h"
using namespace std;
    
#define int int64_t
#define pb push_back

const int llim=3000;
const int lim=40000;
int mod=1e9+7;

const int inf=INT_MAX;

using pii=pair<int,int>;

int cnt=0;

vector<int>v[lim];
int p[llim],initial[llim];
int match[lim],level[llim];

int l,r;

bool dfs(int node){
    if(!node)return 1;
    for(;p[node]<size(v[node])&&v[node][p[node]]<=r;p[node]++){
        int to=v[node][p[node]];
        if(to==match[node])continue;
        int toto=match[to];
        if(level[toto]==level[node]+1&&dfs(toto)){
            match[to]=node;
            match[node]=to;
            return 1;
        }
    }
    return 0;
}

bool ddfs(int node){
    if(!node)return 1;
    for(int j=initial[node];j<size(v[node])&&v[node][j]<=r;j++){
        int to=v[node][j];
        if(to==match[node])continue;
        int toto=match[to];
        if(level[toto]==-1&&(level[toto]=level[node]+1)&&ddfs(toto)){
            match[to]=node;
            match[node]=to;
            return 1;
        }
    }
    return 0;
}

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef Local  
    freopen(".in","r",stdin);freopen(".out","w",stdout);
#endif
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=0;i<k;i++){
        int a,b;
        cin>>a>>b;
        v[b].pb(a+m);
        v[a+m].pb(b);
    }
    for(int i=0;i<=m;i++){
        sort(v[i].begin(),v[i].end());
    }
    int ans=0;
    l=m+1,r=2*m;
    while(cnt!=m&&r<=n+m){
        while(1){
            queue<int>q;
            for(int i=0;i<=m;i++){
                level[i]=-1;
                p[i]=0;
                if(!match[i]&&i){
                    level[i]=0;
                    q.push(i);
                }
            }
            while(q.size()){
                int now=q.front();
                q.pop();
                for(int pp=initial[now];pp<size(v[now])&&v[now][pp]<=r;pp++){
                    int j=v[now][pp];
                    if(j!=match[now]){
                        level[match[j]]=level[now]+1;
                        q.push(match[j]);
                    }
                }
            }
            if(level[0]==-1)break;
            for(int i=1;i<=m;i++){
                if(match[i])continue;
                int val;
                if(val=dfs(i)){
                    cnt+=val;
                }
            }
        }
        if(cnt!=m)r++;
    } 
    if(cnt==m){
        ans+=n+m-r+1;
    }
    if(match[l]){
        match[match[l]]=0;
        match[l]=0;
        cnt--;
    }
    for(int i=1;i<=m;i++){
        if(initial[i]!=size(v[i])&&v[i][initial[i]]==l){
            initial[i]++;
        }
    }
    l++;
    for(;l<n+m;l++){
        if(cnt!=m){
            int lostone=0;
            for(int i=0;i<=m;i++){
                level[i]=-1;
                if(i&&!match[i]){
                    lostone=i;
                    level[i]=0;
                }
            }
            int val=ddfs(lostone);
            if(val){
                cnt++;
            }else{
                while(cnt!=m&&r<n+m){
                    r++;
                    bool found=0;
                    for(int j:v[r]){
                        if(level[j]!=-1){
                            found=1;
                            break;
                        }
                    }
                    if(found){
                        cnt++;
                        for(int i=0;i<=m;i++){
                            level[i]=-1;
                            if(i&&!match[i]){
                                lostone=i;
                                level[i]=0;
                            }
                        }
                        ddfs(lostone);
                    }
                }
            }
        }
        if(cnt==m){
            ans+=n+m-r+1;
        }else break;
        if(match[l]){
            match[match[l]]=0;
            match[l]=0;
            cnt--;
        }
        for(int i=1;i<=m;i++){
            if(initial[i]!=size(v[i])&&v[i][initial[i]]==l){
                initial[i]++;
            }
        }
    }
    cout<<ans<<"\n";
}

Compilation message

marriage.cpp: In function 'bool dfs(int64_t)':
marriage.cpp:25:17: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for(;p[node]<size(v[node])&&v[node][p[node]]<=r;p[node]++){
      |          ~~~~~~~^~~~~~~~~~~~~~
marriage.cpp: In function 'bool ddfs(int64_t)':
marriage.cpp:40:30: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for(int j=initial[node];j<size(v[node])&&v[node][j]<=r;j++){
      |                             ~^~~~~~~~~~~~~~
marriage.cpp: In function 'int main()':
marriage.cpp:85:43: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |                 for(int pp=initial[now];pp<size(v[now])&&v[now][pp]<=r;pp++){
      |                                         ~~^~~~~~~~~~~~~
marriage.cpp:97:23: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   97 |                 if(val=dfs(i)){
      |                    ~~~^~~~~~~
marriage.cpp:113:22: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |         if(initial[i]!=size(v[i])&&v[i][initial[i]]==l){
      |            ~~~~~~~~~~^~~~~~~~~~~~
marriage.cpp:164:26: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |             if(initial[i]!=size(v[i])&&v[i][initial[i]]==l){
      |                ~~~~~~~~~~^~~~~~~~~~~~

Subtask #1
72.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1368 KB Output is correct
2 Correct 1 ms 1368 KB Output is correct
3 Correct 1 ms 1372 KB Output is correct
4 Correct 1 ms 1368 KB Output is correct
5 Correct 0 ms 1372 KB Output is correct
6 Correct 1 ms 1372 KB Output is correct
7 Runtime error 307 ms 262144 KB Execution killed with signal 9
8 Correct 1 ms 1624 KB Output is correct
9 Execution timed out 1582 ms 1372 KB Time limit exceeded
10 Correct 1 ms 1368 KB Output is correct
11 Correct 1 ms 1372 KB Output is correct
12 Correct 1 ms 1372 KB Output is correct
13 Incorrect 1 ms 1372 KB Output isn't correct
14 Runtime error 361 ms 262144 KB Execution killed with signal 9
15 Runtime error 952 ms 262144 KB Execution killed with signal 9
16 Correct 1 ms 1372 KB Output is correct
17 Correct 1 ms 1372 KB Output is correct
18 Correct 1 ms 1372 KB Output is correct
19 Correct 1 ms 1500 KB Output is correct
20 Runtime error 317 ms 262144 KB Execution killed with signal 9
21 Correct 1 ms 1372 KB Output is correct
22 Correct 1 ms 1372 KB Output is correct
23 Correct 1 ms 1372 KB Output is correct
24 Correct 1 ms 1372 KB Output is correct
25 Runtime error 239 ms 262144 KB Execution killed with signal 9
26 Runtime error 338 ms 262144 KB Execution killed with signal 9
27 Correct 1 ms 1372 KB Output is correct
28 Correct 1 ms 1372 KB Output is correct
29 Correct 2 ms 1628 KB Output is correct
30 Correct 2 ms 1628 KB Output is correct
31 Runtime error 246 ms 262144 KB Execution killed with signal 9
32 Runtime error 462 ms 262144 KB Execution killed with signal 9
33 Correct 2 ms 1372 KB Output is correct
34 Correct 4 ms 1372 KB Output is correct
35 Correct 57 ms 4932 KB Output is correct
36 Correct 38 ms 4444 KB Output is correct
37 Runtime error 292 ms 262144 KB Execution killed with signal 9
38 Correct 17 ms 5244 KB Output is correct
39 Correct 108 ms 1620 KB Output is correct
40 Correct 44 ms 1884 KB Output is correct
41 Execution timed out 1536 ms 2808 KB Time limit exceeded
42 Correct 76 ms 2484 KB Output is correct
43 Correct 52 ms 3152 KB Output is correct
44 Correct 123 ms 4500 KB Output is correct
45 Correct 121 ms 2868 KB Output is correct
46 Runtime error 1126 ms 262144 KB Execution killed with signal 9
47 Correct 220 ms 4948 KB Output is correct
48 Correct 205 ms 4744 KB Output is correct
49 Runtime error 1033 ms 262144 KB Execution killed with signal 9
50 Correct 247 ms 1728 KB Output is correct