Submission #345385

#	Time	Username	Problem	Language	Result	Execution time	Memory
345385		vonatlus	Marriage questions (IZhO14_marriage)	C++17	86 / 100	1586 ms	4376 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(mt[to])) {
            mt[to] = x;
            p[x] = to;
            return 1;
        }
    }
    return 0;
}

int n, m, k;

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

void ma1n() {
    cin >> n >> m >> k;
    for (int u, v; k--;) {
        cin >> u >> v;
        u--, v--;
        g[u].pb(v);
    }
    ll ans = 0;
    memset(mt, -1, sizeof(mt));
    for (int i = 0; i < n; ++i) {
        int l = i+m-1;
        int r = n-1;
        int j = -1;            
        while (l <= r) {
            int mid = l+r >> 1;
            if (check(i, mid)) {
                j = mid, r = mid-1;        
            } else {
                l = mid+1;
            }
        }
        if (~j) {
            ans += n-j;
        } else break;
    }
    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;
}

Compilation message (stderr)

marriage.cpp: In function 'void ma1n()':
marriage.cpp:103:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  103 |             int mid = l+r >> 1;
      |                       ~^~

• Subtask 1: 86 / 100