Submission #95448

#	Time	Username	Problem	Language	Result	Execution time	Memory
95448		choikiwon	Marriage questions (IZhO14_marriage)	C++17	36 / 100	1582 ms	263168 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) {
    if(t) {
        if(!chk[u]) {
            chk[u] = 1;
            return true;
        }

        int e = who[u];
        int v = U[e] + V[e] - u;

        if(dfs(v, 0, lb, ub)) {
            matched[e] = 0;
            return true;
        }
        else return false;
    }
    else {
        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(chk[v] && vis[v]) continue;
            if(!matched[e] && dfs(v, 1, lb, ub)) {
                who[u] = e;
                who[v] = e;
                matched[e] = 1;
                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 < M; k++) vis[N + 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;
            chk[v] = 0;
            for(int k = 0; k < M; k++) if(chk[N + k]) {
                int e = who[N + k];
                int x = U[e] + V[e] - (N + k);
                vis[x] = 0;
            }
            if(dfs(v, 0, i + 1, j - 1)) {
                matching++;
                chk[v] = 1;
            }
        }
    }
    printf("%lld", ans);
}

Compilation message (stderr)

marriage.cpp: In function 'bool dfs(int, int, int, int)':
marriage.cpp:29:26: 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:46: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:49: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: 36 / 100