oj.uz

Submission #442988

# Submission time Handle Problem Language Result Execution time Memory
442988 2021-07-09T12:59:06 Z leaked Marriage questions (IZhO14_marriage) C++14
28 / 100
 1372 ms 262148 KB 
#include <bits/stdc++.h>
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("-O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define vec vector
#define sz(x) ( int)x.size()
#define m_p make_pair
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using namespace std;
typedef long long ll;
typedef pair<ll, int> pli;
typedef pair<int,ll> pil;
typedef pair<int,int> pii;
typedef unsigned long long ull;
auto rng=bind(uniform_int_distribution<int>(1,1000),mt19937(time(0)));
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
const int N=3e4+1;
const int K=sqrt(N)+1;
const int M=2001;
vec<int>g[N];
int tt=1;
bool kuhn(int v,short *u,short *mt){
    if(u[v]==tt) return 0;
    u[v]=tt;
    for(auto &z : g[v]){
        if(mt[z]==-1){
            mt[z]=v;
            return 1;
        }
    }
    for(auto &z : g[v]){
        if(kuhn(mt[z],u,mt)){
            mt[z]=v;
            return 1;
        }
    }
    return 0;
}
short mt[N/K+1][M];
short cnt[N/K+1];
short u[N];
short cr[M];
int c=0;
int n,m;
bool check(int l,int r){
    if(r/K>0){
         memcpy(cr,mt[r/K-1],sizeof(mt[r/K-1]));
         c=cnt[r/K-1];
    }
    else{
        fill(cr,cr+M,-1);
        c=0;
    }
    tt++;
    for(int i=max(l,(r/K)*K);i<=r;i++){
        if(kuhn(i,u,cr)) c++;
    }
    return c==m;
}
void add(int id){
    for(int i=id/K;i<=(n-1)/K;i++){
        tt++;
        cnt[i]+=kuhn(id,u,mt[i]);
    }
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int k;
    cin>>n>>m>>k;
    for(int i=0;i<k;i++){
        int v,u;
        cin>>v>>u;--v;--u;
        g[v].pb(u);
    }
    for(int i=0;i<N/K+1;i++){
        for(int j=0;j<m;j++){
            mt[i][j]=-1;
        }
    }
    for(int j=0;j<m;j++) cr[j]=-1;
    int l=n;
    int h=0;
    while(h!=m && l>0){
        l--;
        h+=kuhn(l,u,cr);
    }
    for(int i=n-1;i>l;i--){
        add(i);
    }
    int r=n-1;
    ll ans=0;
//    cerr<<endl;
    for(int i=l;i>=0;i--){
//        cerr<<i<<' '<<r<<endl;
        add(i);
        while(check(i,r-1)) r--;
        ans+=(n-r);
    }
    cout<<ans;
    return 0;
}

/*
5
1 2
2 3
3 4
4 5
5 1
*/

Subtask #1
28.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1612 KB Output isn't correct
2 Incorrect 1 ms 1612 KB Output isn't correct
3 Incorrect 1 ms 1612 KB Output isn't correct
4 Incorrect 1 ms 1612 KB Output isn't correct
5 Correct 1 ms 1664 KB Output is correct
6 Correct 1 ms 1612 KB Output is correct
7 Incorrect 1 ms 1612 KB Output isn't correct
8 Correct 1 ms 1612 KB Output is correct
9 Incorrect 1 ms 1612 KB Output isn't correct
10 Incorrect 1 ms 1612 KB Output isn't correct
11 Correct 1 ms 1612 KB Output is correct
12 Incorrect 1 ms 1612 KB Output isn't correct
13 Correct 1 ms 1612 KB Output is correct
14 Incorrect 1 ms 1612 KB Output isn't correct
15 Incorrect 1 ms 1624 KB Output isn't correct
16 Incorrect 1 ms 1612 KB Output isn't correct
17 Correct 1 ms 1612 KB Output is correct
18 Correct 1 ms 1612 KB Output is correct
19 Incorrect 2 ms 1680 KB Output isn't correct
20 Incorrect 2 ms 1612 KB Output isn't correct
21 Incorrect 1 ms 1612 KB Output isn't correct
22 Incorrect 1 ms 1612 KB Output isn't correct
23 Correct 2 ms 1612 KB Output is correct
24 Correct 1 ms 1612 KB Output is correct
25 Incorrect 18 ms 1884 KB Output isn't correct
26 Incorrect 8 ms 1760 KB Output isn't correct
27 Incorrect 1 ms 1612 KB Output isn't correct
28 Incorrect 1 ms 1672 KB Output isn't correct
29 Correct 14 ms 1740 KB Output is correct
30 Correct 11 ms 1740 KB Output is correct
31 Incorrect 193 ms 2392 KB Output isn't correct
32 Incorrect 47 ms 1740 KB Output isn't correct
33 Incorrect 1 ms 1612 KB Output isn't correct
34 Incorrect 2 ms 1672 KB Output isn't correct
35 Correct 350 ms 3020 KB Output is correct
36 Correct 252 ms 2856 KB Output is correct
37 Incorrect 1372 ms 2524 KB Output isn't correct
38 Correct 1362 ms 3304 KB Output is correct
39 Runtime error 164 ms 262148 KB Execution killed with signal 9
40 Runtime error 169 ms 262148 KB Execution killed with signal 9
41 Runtime error 179 ms 262148 KB Execution killed with signal 9
42 Runtime error 201 ms 262148 KB Execution killed with signal 9
43 Runtime error 237 ms 262148 KB Execution killed with signal 9
44 Runtime error 282 ms 262148 KB Execution killed with signal 9
45 Runtime error 170 ms 262148 KB Execution killed with signal 9
46 Runtime error 411 ms 262148 KB Execution killed with signal 9
47 Runtime error 210 ms 262148 KB Execution killed with signal 9
48 Runtime error 216 ms 262148 KB Execution killed with signal 9
49 Runtime error 579 ms 262148 KB Execution killed with signal 9
50 Runtime error 170 ms 262148 KB Execution killed with signal 9