Submission #172978

#	Time	Username	Problem	Language	Result	Execution time	Memory
172978		VEGAnn	Marriage questions (IZhO14_marriage)	C++14	96 / 100	831 ms	2168 KiB

marriage

#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define PB push_back
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
const int N = 2010;
const int M = 30010;
const int PW = 10;
const int oo = 2e9;
const int md = 998244353;
vector<int> g[N];
queue<int> q;
int n, m, k, mrk[M], used[N], tt = 0, lf, rt;
ll ans = 0;

bool dfs(int v){
    if (used[v] == tt) return 0;
    used[v] = tt;
    for (int u : g[v])
        if (u >= lf && u <= rt && (mrk[u] < 0 || dfs(mrk[u]))){
            mrk[u] = v;
            return 1;
        }
    return 0;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> k;
    for (int i = 0; i < k; i++){
        int x, y;
        cin >> x >> y;
        x--; y--;
        g[y].PB(x);
    }

    fill(mrk, mrk + n, -1);

    for (int i = 0; i < m; i++)
        q.push(i);

    for (int l = 0, r = 0; l < n; l++){

        while (r < n && sz(q)) {
            tt++;
            lf = l; rt = r;
            while (sz(q)) {
                int v = q.front();
                if (dfs(v))
                    q.pop();
                else break;
            }
            if (!sz(q)) break;
            r++;
        }

        if (sz(q))
            break;

        ans += n - r;

        if (mrk[l] >= 0){
            q.push(mrk[l]);
            mrk[l] = -1;
        }
    }

    cout << ans;

    return 0;
}

• Subtask 1: 96 / 100