oj.uz

답안 #1027725

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1027725 2024-07-19T09:29:01 Z caterpillow 결혼 문제 (IZhO14_marriage) C++17
22 / 100
 1500 ms 6228 KB 
#include <bits/stdc++.h>

using namespace std;

using db = long double;
using ll = long long;
using pl = pair<ll, ll>;
using pi = pair<int, int>;
#define vt vector
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end() 
#define size(x) ((int) (x).size())
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0R(i, b) FOR (i, 0, b)
#define endl '\n'
const ll INF = 1e18;
const int inf = 1e9;

template<typename Tuple, size_t... Is>
void print_tuple(const Tuple& t, index_sequence<Is...>) {
    ((cerr << (Is == 0 ? "{" : ", ") << get<Is>(t)), ...);
    cerr << "}";
}

template<typename... Args>
ostream& operator<<(ostream& os, const tuple<Args...>& t) {
    print_tuple(t, index_sequence_for<Args...>{});
    return os;
}

ostream& operator<<(ostream& os, string& s) {
    for (char c : s) os << c; 
    return os;
}

template<template<typename> class Container, typename T>
ostream& operator<<(ostream& os, Container<T> o) {
    os << "{"; 
    int g = size(o); 
    for (auto i : o) os << i << ((--g) == 0 ? "" : ", "); 
    os << "}";
    return os;
}

template<typename T, typename V>
ostream& operator<<(ostream& os, const pair<T, V> p) {
    os << "{" << p.f << ", " << p.s << "}";
    return os;
}

template <typename T, typename... V>
void printer(const char *names, T &&head, V &&...tail) {
    int i = 0;
    while (names[i] != '\0' && names[i] != ',') i++;
    constexpr bool is_str = is_same_v<decay_t<T>, const char*>;
    if constexpr (is_str) cerr << head; // ignore directly passed strings
    else cerr.write(names, i) << " = " << head; 
    if constexpr (sizeof...(tail)) cerr << (is_str ? "" : ","), printer(names + i + 1, tail...);
    else cerr << endl;
}

#ifdef LOCAL
#define dbg(...) std::cerr << __LINE__ << ": ", printer(#__VA_ARGS__, __VA_ARGS__)
#else
#define dbg(x...)
#define cerr if (0) std::cerr
#endif

/*

range perfect matching goes crazy

since kuhn's is more efficient when lhs is small, we need the girls to be on the left
we want to find the maximum r for each l, and two pointer it

*/

int n, m, k; // n is lhs (girls), m is rhs (boys)
vt<unordered_set<int>> adj; // l -> r
vt<int> mate; // mate = rhs -> lhs
vt<bool> seen;

bool dfs(int u) {
    if (seen[u]) return false;
    seen[u] = true;
    for (int v : adj[u]) {
        if (mate[v] == -1 || dfs(mate[v])) {
            mate[v] = u;
            return true;
        }
    }
    return false;
}

bool check_perfect_matching() {
    seen.assign(n, 0);
    mate.assign(m, -1);
    F0R (i, n) {
        if (!dfs(i)) return false;
    }
    return true;
}

main() {
    cin.tie(0)->sync_with_stdio(0);
    
    cin >> m >> n >> k;
    adj.resize(n);
    mate.resize(m, -1);

    vt<vt<int>> radj(m);
    F0R (i, k) {
        int u, v; cin >> u >> v; u--, v--;
        // u is boy, v is girl
        radj[u].pb(v);
    }

    ll ans = 0;
    int r = -1;

    F0R (l, m) {
        while (!check_perfect_matching()) {
            if (r == m - 1) {
                cout << ans << endl;
                return 0;
            }
            r++;

            // add these edges
            for (int u : radj[r]) assert(adj[u].insert(r).s);
        }

        // add # of possible right endpoints for l
        ans += m - r;
        assert(r - l + 1 >= n);

        // remove edges
        for (int u : radj[l]) assert(adj[u].erase(l));
    }
}

Compilation message

marriage.cpp:107:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  107 | main() {
      | ^~~~

Subtask #1
22.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Incorrect 1 ms 348 KB Output isn't correct
14 Incorrect 0 ms 348 KB Output isn't correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Incorrect 0 ms 348 KB Output isn't correct
17 Incorrect 0 ms 348 KB Output isn't correct
18 Incorrect 0 ms 348 KB Output isn't correct
19 Incorrect 1 ms 348 KB Output isn't correct
20 Incorrect 0 ms 348 KB Output isn't correct
21 Correct 1 ms 348 KB Output is correct
22 Incorrect 0 ms 348 KB Output isn't correct
23 Incorrect 1 ms 344 KB Output isn't correct
24 Incorrect 0 ms 348 KB Output isn't correct
25 Incorrect 6 ms 604 KB Output isn't correct
26 Incorrect 1 ms 348 KB Output isn't correct
27 Correct 1 ms 344 KB Output is correct
28 Incorrect 1 ms 348 KB Output isn't correct
29 Incorrect 2 ms 720 KB Output isn't correct
30 Incorrect 2 ms 752 KB Output isn't correct
31 Incorrect 66 ms 1884 KB Output isn't correct
32 Incorrect 6 ms 604 KB Output isn't correct
33 Correct 1 ms 348 KB Output is correct
34 Incorrect 2 ms 604 KB Output isn't correct
35 Incorrect 20 ms 5096 KB Output isn't correct
36 Incorrect 17 ms 4444 KB Output isn't correct
37 Incorrect 155 ms 1884 KB Output isn't correct
38 Incorrect 32 ms 5208 KB Output isn't correct
39 Incorrect 94 ms 1116 KB Output isn't correct
40 Correct 50 ms 1512 KB Output is correct
41 Incorrect 69 ms 1872 KB Output isn't correct
42 Incorrect 128 ms 2644 KB Output isn't correct
43 Incorrect 117 ms 3152 KB Output isn't correct
44 Incorrect 204 ms 5204 KB Output isn't correct
45 Incorrect 805 ms 2956 KB Output isn't correct
46 Incorrect 1316 ms 3560 KB Output isn't correct
47 Incorrect 489 ms 6228 KB Output isn't correct
48 Incorrect 476 ms 5972 KB Output isn't correct
49 Execution timed out 1560 ms 3412 KB Time limit exceeded
50 Incorrect 463 ms 1616 KB Output isn't correct