Submission #363296

#	Time	Username	Problem	Language	Result	Execution time	Memory
363296		SamAnd	Marriage questions (IZhO14_marriage)	C++17	100 / 100	317 ms	1132 KiB

marriage

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 30004, M = 2003;

int n, m, k;
vector<int> g[M];

int u[N];
int uu[M];
bool c[M];
int s[N];
bool dfs(int x, int l, int r)
{
    if (c[x])
        return false;
    c[x] = true;
    while (s[x] < sz(g[x]) && g[x][s[x]] < l)
        ++s[x];
    for (int i = s[x]; i < g[x].size(); ++i)
    {
        int h = g[x][i];
        if (h > r)
            break;
        if (u[h] == 0)
        {
            u[h] = x;
            uu[x] = h;
            return true;
        }
        else
        {
            if (dfs(u[h], l, r))
            {
                u[h] = x;
                uu[x] = h;
                return true;
            }
        }
    }
    return false;
}

void solv()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < k; ++i)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        g[y].push_back(x);
    }
    for (int i = 1; i <= m; ++i)
        sort(all(g[i]));

    int ans = 0;
    int r = 0;
    queue<int> q;
    for (int i = 1; i <= m; ++i)
        q.push(i);
    for (int l = 1; l <= n; ++l)
    {
        while (1)
        {
            while (1)
            {
                if (q.empty())
                    break;
                memset(c, false, sizeof c);
                if (dfs(q.front(), l, r))
                {
                    q.pop();
                    continue;
                }
                break;
            }
            if (q.empty())
                break;
            ++r;
            if (r == n + 1)
                break;
        }
        if (r == n + 1)
            break;
        ans += (n - r + 1);
        if (u[l])
        {
            q.push(u[l]);
            uu[u[l]] = 0;
            u[l] = 0;
        }
    }
    printf("%d\n", ans);
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    //ios_base::sync_with_stdio(false), cin.tie(0);
    solv();
    return 0;
}

Compilation message (stderr)

marriage.cpp: In function 'bool dfs(int, int, int)':
marriage.cpp:27:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for (int i = s[x]; i < g[x].size(); ++i)
      |                        ~~^~~~~~~~~~~~~
marriage.cpp: In function 'void solv()':
marriage.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   53 |     scanf("%d%d%d", &n, &m, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
marriage.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   57 |         scanf("%d%d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100