Submission #39617459

Source Code Expand

#include <bits/stdc++.h>
#include <stdio.h>
// #include <boost/multiprecision/cpp_int.hpp>
// using Bint = boost::multiprecision::cpp_int;
#define ALL(v) (v).begin(), (v).end()
#define OVERLOAD4(_1, _2, _3, _4, name, ...) name
#define REP1(n) for (int i = 0; i < n; i++)
#define REP2(i, n) for (int i = 0; i < n; i++)
#define REP3(i, a, b) for (int i = a; i < b; i++)
#define REP4(i, a, b, c) for (int i = a; i < b; i += c)
#define REP(...) OVERLOAD4(__VA_ARGS__, REP4, REP3, REP2, REP1)(__VA_ARGS__)
#define ll long long
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const int INF = 1000000000;
const ll LINF = 1000000000000000000;  // 1e18
const double PI = acos(-1.0);
const double EPS = 1e-10;

template<class T> inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
inline constexpr ll ceil_div(const ll a, const ll b) {
    return (a + b - 1) / b - !!((a + b - 1) % b < 0);
}  // return ceil(a/b)
inline constexpr ll floor_div(const ll a, const ll b) { return a / b - !!(a % b < 0); }  // return floor(a/b)

/*  ----------------------- DEBUG FUNCTION ---------------------------- */
#define DUMPOUT cerr
void dump_function() { DUMPOUT << ' '; }
void dump_function(bool a) { DUMPOUT << a; }
void dump_function(int a) { DUMPOUT << a; }
void dump_function(long long a) { DUMPOUT << a; }
void dump_function(char a) { DUMPOUT << a; }
void dump_function(string &a) { DUMPOUT << a; }
void dump_function(double a) { DUMPOUT << a; }
template<class T> void dump_function(const vector<T> &);
template<class T, size_t size> void dump_function(const array<T, size> &);
template<class T, class L> void dump_function(const pair<T, L> &p);
template<class T, size_t size> void dump_function(const T (&)[size]);
template<class T> void dump_function(const vector<T> &a) {
    if (a.empty()) return;
    dump_function(a[0]);
    for (auto i = a.begin(); ++i != a.end();) {
        DUMPOUT << " ";
        dump_function(*i);
    }
    DUMPOUT << endl;
}
template<class T> void dump_function(const deque<T> &a) {
    if (a.empty()) return;
    dump_function(a[0]);
    for (auto i = a.begin(); ++i != a.end();) {
        DUMPOUT << " ";
        dump_function(*i);
    }
}
template<class T, size_t size> void dump_function(const array<T, size> &a) {
    dump_function(a[0]);
    for (auto i = a.begin(); ++i != a.end();) {
        DUMPOUT << " ";
        dump_function(*i);
    }
}
template<class T, class L> void dump_function(const pair<T, L> &p) {
    DUMPOUT << '(';
    dump_function(p.first);
    DUMPOUT << ",";
    dump_function(p.second);
    DUMPOUT << ')';
}
template<class T> void dump_function(set<T> &x) {
    for (auto e : x)
        dump_function(e), DUMPOUT << " ";
    DUMPOUT << endl;
}
template<class T> void dump_function(multiset<T> &x) {
    for (auto e : x)
        dump_function(e), DUMPOUT << " ";
    DUMPOUT << endl;
}
template<class T, size_t size> void dump_function(const T (&a)[size]) {
    dump_function(a[0]);
    for (auto i = a; ++i != end(a);) {
        DUMPOUT << " ";
        dump_function(*i);
    }
}
template<class T> void dump_function(const T &a) { DUMPOUT << a; }
int dump_out() {
    DUMPOUT << '\n';
    return 0;
}
template<class T> int dump_out(const T &t) {
    dump_function(t);
    DUMPOUT << '\n';
    return 0;
}
template<class Head, class... Tail> int dump_out(const Head &head, const Tail &...tail) {
    dump_function(head);
    DUMPOUT << ' ';
    dump_out(tail...);
    return 0;
}

#ifdef DEBUG_
#define dump(x)                                                                                                        \
    DUMPOUT << #x << ": ";                                                                                             \
    dump_function(x);                                                                                                  \
    DUMPOUT << endl;
void dumps() { }
template<class T> void dumps(const T &t) {
    dump_function(t);
    DUMPOUT << " ";
}
template<class Head, class... Tail> void dumps(const Head &head, const Tail &...tail) {
    dump_function(head);
    DUMPOUT << ' ';
    dump_out(tail...);
}
#else
#define dump(x)
template<class... T> void dumps(const T &...) { }
#endif
/*  ----------------------- DEBUG FUNCTION ---------------------------- */

template<int MOD> struct Fp {
    long long val;
    constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
        if (val < 0) val += MOD;
    }
    constexpr int getmod() const { return MOD; }
    constexpr Fp operator-() const noexcept { return val ? MOD - val : 0; }
    constexpr Fp operator+(const Fp &r) const noexcept { return Fp(*this) += r; }
    constexpr Fp operator-(const Fp &r) const noexcept { return Fp(*this) -= r; }
    constexpr Fp operator*(const Fp &r) const noexcept { return Fp(*this) *= r; }
    constexpr Fp operator/(const Fp &r) const noexcept { return Fp(*this) /= r; }
    constexpr Fp &operator+=(const Fp &r) noexcept {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp &operator-=(const Fp &r) noexcept {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp &operator*=(const Fp &r) noexcept {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr Fp &operator/=(const Fp &r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b, swap(a, b);
            u -= t * v, swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr bool operator==(const Fp &r) const noexcept { return this->val == r.val; }
    constexpr bool operator!=(const Fp &r) const noexcept { return this->val != r.val; }
    friend constexpr istream &operator>>(istream &is, Fp<MOD> &x) noexcept {
        is >> x.val;
        x.val %= MOD;
        if (x.val < 0) x.val += MOD;
        return is;
    }
    friend constexpr ostream &operator<<(ostream &os, const Fp<MOD> &x) noexcept { return os << x.val; }
    friend constexpr Fp<MOD> modpow(const Fp<MOD> &r, long long n) noexcept {
        if (n == 0) return 1;
        auto t = modpow(r, n / 2);
        t = t * t;
        if (n & 1) t = t * r;
        return t;
    }
    friend constexpr Fp<MOD> modinv(const Fp<MOD> &r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b, swap(a, b);
            u -= t * v, swap(u, v);
        }
        return Fp<MOD>(u);
    }
};

template<class T> struct BiCoef {
    vector<T> fact_, inv_, finv_;
    constexpr BiCoef() { }
    constexpr BiCoef(int n) noexcept : fact_(n, 1), inv_(n, 1), finv_(n, 1) { init(n); }
    constexpr void init(int n) noexcept {
        fact_.assign(n, 1), inv_.assign(n, 1), finv_.assign(n, 1);
        int MOD = fact_[0].getmod();
        for (int i = 2; i < n; i++) {
            fact_[i] = fact_[i - 1] * i;
            inv_[i] = -inv_[MOD % i] * (MOD / i);
            finv_[i] = finv_[i - 1] * inv_[i];
        }
    }
    constexpr T nCr(int n, int k) const noexcept {
        if (n < k || n < 0 || k < 0) return 0;
        int MOD = fact_[0].getmod();
        if (n < MOD) return fact_[n] * finv_[k] * finv_[n - k];

        // Lucasの定理
        T ret = 1;
        while (n || k) {
            int _n = n % MOD, _k = k % MOD;
            n /= MOD;
            k /= MOD;
            ret *= nCr(_n, _k);
        }
        return ret;
    }
    constexpr T nPr(int n, int k) const noexcept {
        if (n < k || n < 0 || k < 0) return 0;
        return fact_[n] * finv_[n - k];
    }
    constexpr T nHr(int n, int k) const noexcept {
        if (n <= 0 || k < 0) return 0;
        return nCr(n + k - 1, k);
    }
    constexpr T fact(int n) const noexcept {
        if (n < 0) return 0;
        return fact_[n];
    }
    constexpr T inv(int n) const noexcept {
        if (n < 0) return 0;
        return inv_[n];
    }
    constexpr T finv(int n) const noexcept {
        if (n < 0) return 0;
        return finv_[n];
    }
};

/* ----------------------------- MOD ----------------------------------- */
const int MOD = 1000000007;
const int MOD2 = 998244353;
using mint = Fp<MOD2>;
BiCoef<mint> bc;
// using vec = vector<int>;
// using mat = vector<vec>;
/* ----------------------------- MOD ----------------------------------- */

/*  ----------------------- AtCoder Library ---------------------------- */
// #include <atcoder/all>
// using namespace atcoder;
/*  ----------------------- AtCoder Library ---------------------------- */
struct UnionFind {
    vector<int> par;

    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }

    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }

    bool issame(int x, int y) { return root(x) == root(y); }

    bool unite(int x, int y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y);  // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }

    int size(int x) { return -par[root(x)]; }
};

void solve() {
    int N, M;
    cin >> N >> M;
    UnionFind uf(2 * N);
    REP(i, N) uf.unite(i, N + i);
    vector<int> a(M), c(M);
    vector<char> b(M), d(M);
    REP(i, M) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        --a[i], --c[i];
        int na = (b[i] == 'R' ? a[i] : N + a[i]);
        int nc = (d[i] == 'R' ? c[i] : N + c[i]);
        uf.unite(na, nc);
    }
    set<int> root;
    vector<int> edge(2 * N);
    REP(i, N) {
        root.emplace(uf.root(i));
        edge[uf.root(i)]++;
    }
    REP(i, M) edge[uf.root(a[i])]++;
    int X = 0, Y = root.size();
    for (auto x : root) {
        if (edge[x] == uf.size(x)) {
            X++;
            Y--;
        }
    }
    cout << X << " " << Y << endl;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    solve();
    // int T; cin >> T; REP(t,T) solve();
}

Submission Info

Submission Time
Task D - Tying Rope
User Bondo416
Language C++ (GCC 9.2.1)
Score 400
Code Size 10647 Byte
Status AC
Exec Time 95 ms
Memory 17684 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status AC
AC × 31
Set Name Test Cases
Sample
All sample00.txt, sample01.txt, sample02.txt, testcase00.txt, testcase01.txt, testcase02.txt, testcase03.txt, testcase04.txt, testcase05.txt, testcase06.txt, testcase07.txt, testcase08.txt, testcase09.txt, testcase10.txt, testcase11.txt, testcase12.txt, testcase13.txt, testcase14.txt, testcase15.txt, testcase16.txt, testcase17.txt, testcase18.txt, testcase19.txt, testcase20.txt, testcase21.txt, testcase22.txt, testcase23.txt, testcase24.txt, testcase25.txt, testcase26.txt, testcase27.txt
Case Name Status Exec Time Memory
sample00.txt AC 14 ms 3548 KiB
sample01.txt AC 2 ms 3648 KiB
sample02.txt AC 2 ms 3552 KiB
testcase00.txt AC 63 ms 8116 KiB
testcase01.txt AC 64 ms 8068 KiB
testcase02.txt AC 57 ms 15576 KiB
testcase03.txt AC 95 ms 17684 KiB
testcase04.txt AC 32 ms 5416 KiB
testcase05.txt AC 35 ms 5468 KiB
testcase06.txt AC 41 ms 5556 KiB
testcase07.txt AC 30 ms 9116 KiB
testcase08.txt AC 31 ms 5552 KiB
testcase09.txt AC 59 ms 7952 KiB
testcase10.txt AC 64 ms 8040 KiB
testcase11.txt AC 63 ms 7800 KiB
testcase12.txt AC 61 ms 11876 KiB
testcase13.txt AC 33 ms 5836 KiB
testcase14.txt AC 62 ms 8152 KiB
testcase15.txt AC 65 ms 8196 KiB
testcase16.txt AC 68 ms 8180 KiB
testcase17.txt AC 64 ms 11908 KiB
testcase18.txt AC 39 ms 5404 KiB
testcase19.txt AC 66 ms 8196 KiB
testcase20.txt AC 65 ms 7920 KiB
testcase21.txt AC 73 ms 8044 KiB
testcase22.txt AC 71 ms 11500 KiB
testcase23.txt AC 50 ms 10232 KiB
testcase24.txt AC 78 ms 12292 KiB
testcase25.txt AC 77 ms 12264 KiB
testcase26.txt AC 85 ms 12748 KiB
testcase27.txt AC 67 ms 15984 KiB