Submission #95474

#	Time	Username	Problem	Language	Result	Execution time	Memory
95474		choikiwon	Marriage questions (IZhO14_marriage)	C++17	100 / 100	788 ms	4728 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];
int vis[MN], who[MN], timer;
vector<int> rem;

bool dfs(int u, int l, int r) {
    if(vis[u] == timer) return false;
    vis[u] = timer;

    for(int i = 0; i < adj[u].size(); i++) {
        int v = adj[u][i];
        if(v < l || r < v) continue;

        if(who[v] == -1 || dfs(who[v], l, r)) {
            who[v] = u;
            return true;
        }
    }
    return false;
}

bool check(int l, int r) {
    while(rem.size()) {
        int t = rem.back(); rem.pop_back();

        timer++;
        if(!dfs(t, l, r)) {
            rem.push_back(t);
            return false;
        }
    }
    return true;
}

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[b].push_back(a);
    }
    memset(who, -1, sizeof(who));

    for(int i = 0; i < M; i++) rem.push_back(i);
    ll ans = 0;
    int j = 0;
    for(int i = 0; i < N; i++) {
        while(j <= N && !check(i, j - 1)) j++;
        if(rem.size()) break;
        ans += N - j + 1;

        if(who[i] != -1) {
            rem.push_back(who[i]);
        }
    }
    printf("%lld", ans);
}

Compilation message (stderr)

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