제출 #345360

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
345360		vonatlus	결혼 문제 (IZhO14_marriage)	C++17	38 / 100	1598 ms	4204 KiB

marriage

/// wa 

#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:36777216")

#include<bits/stdc++.h>

#define x first
#define y second
#define pb push_back
#define sz(x) (int) x.size()
#define all(z) (z).begin(), (z).end()
 
using namespace std;

using ll = long long;
using pii = pair<int, int>;                                   

const int MOD = 1e9 + 7; 
const int INF = 1e9 + 1e2;
  
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void fin() {
#ifdef AM
    freopen(".in", "r", stdin);
#endif        
}                   

const bool flag = 0;

const int N = 5e4+10;

int was[N];

int mt[N], p[N], tmp;

vector<int> adj[N], g[N];
                     
bool dfs(int x) {
    if (was[x] == tmp) return 0;
    was[x] = tmp;
    for (int to : adj[x]) {
        if (mt[to] == -1) {
            mt[to] = x;
            p[x] = to;
            return 1;
        }
    }
    for (int to : adj[x]) {
        if (dfs(to)) {
            mt[to] = x;
            p[x] = to;
            return 1;
        }
    }
    return 0;
}

int n, m, k;

bool check(int l, int r) {
    for (int i = l; i <= r; ++i) {
        for (int to : g[i]) {
            adj[to].pb(i);
        }
    }
    fill(p, p+m, -1);
    for (int i = 0; i < m; ++i) {
        tmp++;
        dfs(i);
    }
    int ok = 1;
    for (int i = 0; i < m; ++i) {
        if (~p[i]) {
            mt[p[i]] = -1;
        } else {          
            ok = 0;
        }
    }
    for (int i = l; i <= r; ++i) {
        for (int to : g[i]) {
            adj[to].pop_back();
        }
    }
    return ok;
}

void ma1n() {
    cin >> n >> m >> k;
    for (int u, v; k--;) {
        cin >> u >> v;
        u--, v--;
        g[u].pb(v);
    }
    int r = 0;
    ll ans = 0;
    memset(mt, -1, sizeof(mt));
    for (int l = 0; l < n; ++l) {
        while (r < n && !check(l, r)) {
            r++;
        }        
        if (check(l, r)) {
            ans += n-r;
        }
    }
    cout << ans;
} 

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr), fin();
    int ts = 1;
    if (flag) {
        cin >> ts;
    }
    while (ts--) {
        ma1n(); 
    }
    return 0;
}

• Subtask 1: 38 / 100