oj.uz

Submission #443061

# Submission time Handle Problem Language Result Execution time Memory
443061 2021-07-09T14:57:07 Z leaked Marriage questions (IZhO14_marriage) C++14
34 / 100
 40 ms 2884 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=165;
const int M=2001;
vec<int> g[N+M];
int uk;
int mt[N+M];
int h[N+M],u[N+M],tt,n,m;
int tr;
vec<int>rem;
bool kuhn(int v){
    if(u[v]==tt) return 0;
    u[v]=tt;
    for(auto &z : g[v]){
        if(h[z] && mt[z]==v) return 1;
    }
    for(auto &z : g[v]){
        if(h[z] && (mt[z]==-1 || kuhn(mt[z]))){
            mt[z]=v;mt[v]=z;
            return 1;
        }
    }
    return 0;
}
signed main(){
//    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int k;
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<k;i++){
        int v,u;
        scanf("%d%d",&v,&u);--v;--u;
        g[v].pb(u+n);
        g[u+n].pb(v);
    }
    fill(mt,mt+n+m,-1);
    for(int i=0;i<m;i++) h[i+n]=1,rem.pb(i+n);
    int r=-1;
    int c=0;
    ll ans=0;
    for(int l=0;l<n;l++){
        if(l){
            h[l-1]=0;
            if(mt[l-1]!=-1){
                tt++;
                rem.pb(mt[l-1]);
                mt[rem.back()]=-1;
                mt[l-1]=-1;
            }
        }
        while(sz(rem) && kuhn(rem.back())){
            rem.pop_back();
        }
        while(r<n && sz(rem)){
            r++;tt++;h[r]=1;
            while(sz(rem) && kuhn(rem.back())){
                rem.pop_back();
            }
        }
        ans+=n-r;
    }
    printf("%lld",ans);
    return 0;
}

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

Compilation message

marriage.cpp: In function 'int main()':
marriage.cpp:59:9: warning: unused variable 'c' [-Wunused-variable]
   59 |     int c=0;
      |         ^
marriage.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |     scanf("%d%d%d",&n,&m,&k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
marriage.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         scanf("%d%d",&v,&u);--v;--u;
      |         ~~~~~^~~~~~~~~~~~~~

Subtask #1
34.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 972 KB Output isn't correct
2 Incorrect 1 ms 972 KB Output isn't correct
3 Incorrect 1 ms 972 KB Output isn't correct
4 Incorrect 1 ms 972 KB Output isn't correct
5 Correct 1 ms 972 KB Output is correct
6 Correct 1 ms 972 KB Output is correct
7 Incorrect 1 ms 972 KB Output isn't correct
8 Correct 1 ms 972 KB Output is correct
9 Incorrect 1 ms 972 KB Output isn't correct
10 Incorrect 1 ms 1020 KB Output isn't correct
11 Incorrect 1 ms 972 KB Output isn't correct
12 Correct 1 ms 972 KB Output is correct
13 Correct 1 ms 972 KB Output is correct
14 Incorrect 1 ms 972 KB Output isn't correct
15 Incorrect 1 ms 972 KB Output isn't correct
16 Incorrect 1 ms 972 KB Output isn't correct
17 Incorrect 1 ms 972 KB Output isn't correct
18 Incorrect 1 ms 972 KB Output isn't correct
19 Incorrect 1 ms 1100 KB Output isn't correct
20 Incorrect 2 ms 972 KB Output isn't correct
21 Correct 1 ms 972 KB Output is correct
22 Incorrect 1 ms 972 KB Output isn't correct
23 Incorrect 1 ms 972 KB Output isn't correct
24 Incorrect 1 ms 972 KB Output isn't correct
25 Incorrect 4 ms 1228 KB Output isn't correct
26 Incorrect 2 ms 1100 KB Output isn't correct
27 Correct 1 ms 972 KB Output is correct
28 Incorrect 1 ms 972 KB Output isn't correct
29 Correct 3 ms 1100 KB Output is correct
30 Correct 3 ms 1100 KB Output is correct
31 Incorrect 14 ms 1556 KB Output isn't correct
32 Incorrect 2 ms 1100 KB Output isn't correct
33 Correct 1 ms 1100 KB Output is correct
34 Incorrect 1 ms 1100 KB Output isn't correct
35 Incorrect 21 ms 2144 KB Output isn't correct
36 Incorrect 19 ms 2052 KB Output isn't correct
37 Incorrect 14 ms 1740 KB Output isn't correct
38 Correct 22 ms 2268 KB Output is correct
39 Incorrect 2 ms 1228 KB Output isn't correct
40 Correct 4 ms 1356 KB Output is correct
41 Incorrect 8 ms 1556 KB Output isn't correct
42 Correct 12 ms 1676 KB Output is correct
43 Correct 18 ms 1868 KB Output is correct
44 Correct 27 ms 2316 KB Output is correct
45 Incorrect 13 ms 2124 KB Output isn't correct
46 Incorrect 40 ms 2804 KB Output isn't correct
47 Correct 37 ms 2656 KB Output is correct
48 Correct 33 ms 2744 KB Output is correct
49 Incorrect 38 ms 2884 KB Output isn't correct
50 Incorrect 3 ms 1356 KB Output isn't correct