Submission #442988

#TimeUsernameProblemLanguageResultExecution timeMemory
442988leakedMarriage questions (IZhO14_marriage)C++14
28 / 100
1372 ms262148 KiB
#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 */
#Verdict Execution timeMemoryGrader output
Fetching results...