Submission #582079

#	Time	Username	Problem	Language	Result	Execution time	Memory
582079		FatihSolak	Marriage questions (IZhO14_marriage)	C++17	100 / 100	158 ms	1732 KiB

marriage

#include <bits/stdc++.h>
#define N 30005
using namespace std;
vector<int> adj[N];
int mt[N];
int l,r;
bool vis[N];
void reset(int x){
    for(int i = 0;i<=x;i++){
        vis[i] = 0;
    }
}
bool try_kuhn(int v){
    if(vis[v])
        return 0;
    vis[v] = 1;
    for(auto u:adj[v]){
        if(u < l || r < u)continue;
        if(mt[u] == 0 || try_kuhn(mt[u])){
            mt[u] = v;
            return 1;
        }
    }
    return 0;
}
void solve(){
    int n,m,k;
    cin >> n >> m >> k;
    for(int i = 1;i<=k;i++){
        int u,v;
        cin >> u >> v;
        adj[v].push_back(u);
    }
    vector<int> unmatched;
    for(int i = 1;i<=m;i++){
        unmatched.push_back(i);
    }
    r = 0;
    int ans = 0;
    for(int i = 1;i<=n;i++){
        l = i;
        r = max(r,i+m-1);
        reset(m);
        while(unmatched.size() && try_kuhn(unmatched.back())){
            reset(m);
            unmatched.pop_back();
        }
        while(r < n && unmatched.size()){
            r++;
            reset(m);
            while(unmatched.size() && try_kuhn(unmatched.back())){
                reset(m);
                unmatched.pop_back();
            }
        }
        if(unmatched.size())break;
        ans += n - r + 1;
        if(mt[i]){
            unmatched.push_back(mt[i]);
        }
    }
    cout << ans;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef Local
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    #ifdef Local
        cout << endl << fixed << setprecision(2) << 1000.0*clock()/CLOCKS_PER_SEC << " milliseconds.";
    #endif
}

• Subtask 1: 100 / 100