Submission 140725 | MatCom Online Grader

Id	Date	User	Problem	Result	Time	Mem	Lang
140725	31/10/2019 8:23:45	jc	A - A pumpkin game	Accepted	15	472.0 KiB	GNU G++17 7.3.0

Code

/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author jcg
 */

#include <iostream>

#include <iostream>
#include <vector>
#include <functional>

struct disjoint_set
{
    std::vector<int> p;

disjoint_set(int n) : p(n, -1) {}

int root(int u) { return p[u] < 0 ? u : p[u] = root(p[u]); }

bool merge(int u, int v)
    {
        if ((u = root(u)) == (v = root(v)))
            return false;
        if (p[u] > p[v])
            std::swap(u, v);
        p[u] += p[v];
        p[v] = u;
        return true;
    }
};

int maximum_bipartite_matching(const std::vector<std::vector<int>> &g, int R)
{
    std::vector<int> mate(R, -1), seen(g.size());
    std::function<bool(int)> augment = [&](int u)
    {
        seen[u] = true;
        for (int v : g[u])
            if (mate[v] == -1 || (!seen[mate[v]] && augment(mate[v])))
            {
                mate[v] = u;
                return true;
            }
        return false;
    };
    int matching_size = 0;
    for (int u = 0; u < (int) g.size(); ++u)
        if (!seen[u] && augment(u))
        {
            ++matching_size;
            std::fill(seen.begin(), seen.end(), 0);
        }
    return matching_size;
}

class TaskA
{
public:
    void solve(std::istream& in, std::ostream& out)
    {
        int N, M;
        in >> N >> M;
        disjoint_set ds(N + N);
        std::vector<std::vector<int>> g(N);
        for (int i = 0; i < M; ++i)
        {
            int x, y;
            in >> x >> y;
            --x, --y;
            ds.merge(x, y + N);
            g[x].emplace_back(y);
        }
        int connected_components = 0;
        for (int u = 0; u < N; ++u)
            if (ds.root(u) == u && g[u].size()) ++connected_components;
        out << connected_components << ' ' << maximum_bipartite_matching(g, N) << '\n';
    }
};

int main()
{
    std::ios_base::sync_with_stdio(0);
    std::istream& in(std::cin);
    std::ostream& out(std::cout);
    in.tie(0);
    TaskA solver;
    solver.solve(in, out);
    return 0;
}

Judgement Details

Case#1 [425984 bytes][0 ms]: ok 2 tokens
Case#2 [430080 bytes][0 ms]: ok 2 tokens
Case#3 [462848 bytes][0 ms]: ok 2 tokens
Case#4 [425984 bytes][0 ms]: ok 2 tokens
Case#5 [425984 bytes][0 ms]: ok 2 tokens
Case#6 [425984 bytes][0 ms]: ok 2 tokens
Case#7 [425984 bytes][0 ms]: ok 2 tokens
Case#8 [425984 bytes][0 ms]: ok 2 tokens
Case#9 [425984 bytes][0 ms]: ok 2 tokens
Case#10 [430080 bytes][0 ms]: ok 2 tokens
Case#11 [425984 bytes][0 ms]: ok 2 tokens
Case#12 [425984 bytes][0 ms]: ok 2 tokens
Case#13 [425984 bytes][0 ms]: ok 2 tokens
Case#14 [425984 bytes][0 ms]: ok 2 tokens
Case#15 [425984 bytes][0 ms]: ok 2 tokens
Case#16 [425984 bytes][0 ms]: ok 2 tokens
Case#17 [430080 bytes][15 ms]: ok 2 tokens
Case#18 [425984 bytes][0 ms]: ok 2 tokens
Case#19 [471040 bytes][0 ms]: ok 2 tokens
Case#20 [458752 bytes][0 ms]: ok 2 tokens
Case#21 [462848 bytes][0 ms]: ok 2 tokens
Case#22 [438272 bytes][0 ms]: ok 2 tokens
Case#23 [458752 bytes][0 ms]: ok 2 tokens
Case#24 [442368 bytes][0 ms]: ok 2 tokens
Case#25 [458752 bytes][0 ms]: ok 2 tokens
Case#26 [458752 bytes][0 ms]: ok 2 tokens
Case#27 [458752 bytes][0 ms]: ok 2 tokens
Case#28 [442368 bytes][0 ms]: ok 2 tokens
Case#29 [425984 bytes][0 ms]: ok 2 tokens
Case#30 [425984 bytes][0 ms]: ok 2 tokens
Case#31 [430080 bytes][0 ms]: ok 2 tokens
Case#32 [442368 bytes][15 ms]: ok 2 tokens
Case#33 [434176 bytes][0 ms]: ok 2 tokens
Case#34 [458752 bytes][0 ms]: ok 2 tokens
Case#35 [458752 bytes][0 ms]: ok 2 tokens
Case#36 [458752 bytes][0 ms]: ok 2 tokens
Case#37 [462848 bytes][0 ms]: ok 2 tokens
Case#38 [458752 bytes][15 ms]: ok 2 tokens
Case#39 [458752 bytes][0 ms]: ok 2 tokens
Case#40 [462848 bytes][0 ms]: ok 2 tokens
Case#41 [458752 bytes][0 ms]: ok 2 tokens
Case#42 [458752 bytes][0 ms]: ok 2 tokens
Case#43 [462848 bytes][0 ms]: ok 2 tokens
Case#44 [430080 bytes][0 ms]: ok 2 tokens
Case#45 [425984 bytes][0 ms]: ok 2 tokens
Case#46 [430080 bytes][0 ms]: ok 2 tokens
Case#47 [425984 bytes][0 ms]: ok 2 tokens
Case#48 [430080 bytes][0 ms]: ok 2 tokens
Case#49 [483328 bytes][0 ms]: ok 2 tokens
Case#50 [466944 bytes][0 ms]: ok 2 tokens

Matcom Online Grader Faculty of Mathematics and Computer Science of University of Havana

Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana