Submission #95441

#	Time	Username	Problem	Language	Result	Execution time	Memory
95441		choikiwon	Marriage questions (IZhO14_marriage)	C++17	48 / 100	1569 ms	5864 KiB

marriage

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MN = 100010;

int N, M, K;
vector<int> adj[MN], U, V;
int matched[MN], chk[MN], who[MN], vis[MN];

bool dfs(int u, int t, int lb, int ub) {
    vis[u] = 1;
    if(t && !chk[u]) {
        chk[u] = 1;
        return true;
    }

    for(int i = 0; i < adj[u].size(); i++) {
        int e = adj[u][i];
        int v = U[e] + V[e] - u;
        if(v < N && (v < lb || ub < v)) continue;
        if(vis[v]) continue;
        if(matched[e] == t && dfs(v, t ^ 1, lb, ub)) {
            if(!t) {
                matched[e] = 1;
                who[u] = e;
                who[v] = e;
            }
            return true;
        }
    }
    return false;
}

int main() {
    scanf("%d %d %d", &N, &M, &K);

    for(int i = 0; i < K; i++) {
        int a, b; scanf("%d %d", &a, &b);
        a--; b--;

        adj[a].push_back(i);
        adj[b + N].push_back(i);
        U.push_back(a);
        V.push_back(b + N);
    }

    ll ans = 0;
    int matching = 0;
    int j = 0;
    for(int i = 0; i < N; i++) {
        while(j < N && matching < M) {
            for(int k = 0; k < N + M; k++) vis[k] = 0;
            if(dfs(j, 0, i, j)) {
                matching++;
                chk[j] = 1;
            }
            j++;
        }
        if(matching < M) break;
        ans += N - j + 1;

        if(chk[i]) {
            matching--;
            int v = U[ who[i] ] + V[ who[i] ] - i;
            matched[ who[i] ] = 0;
            chk[v] = 0;
            for(int k = 0; k < N + M; k++) vis[k] = 0;
            if(dfs(v, 0, i + 1, j)) {
                matching++;
                chk[v] = 1;
            }
        }
    }
    printf("%lld", ans);
}

Compilation message (stderr)

marriage.cpp: In function 'bool dfs(int, int, int, int)':
marriage.cpp:19:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < adj[u].size(); i++) {
                    ~~^~~~~~~~~~~~~~~
marriage.cpp: In function 'int main()':
marriage.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &N, &M, &K);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
marriage.cpp:40:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int a, b; scanf("%d %d", &a, &b);
                   ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 48 / 100