oj.uz

답안 #700918

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
700918 2023-02-19T12:09:58 Z KiriLL1ca 결혼 문제 (IZhO14_marriage) C++17
14 / 100
 52 ms 3924 KB 
#include <bits/stdc++.h>
#define fr first
#define sc second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define endl '\n'
#define sz(x) (int)((x).size())
#define vec vector
#define pw(x) (1ll << x)

using namespace std;

template <typename T> inline bool umin (T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
template <typename T> inline bool umax (T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;

const int N = 3e4 + 2e3 + 10;
vec <int> g[N];
int used[N], mt[N], active[N], us = 0;

inline bool kuhn (int v) {
    if (used[v] == us) return 0;
    used[v] = us;
    for (auto &u : g[v]) if (active[u] && !~mt[u]) { mt[u] = v; return 1; }
    for (auto &u : g[v]) if (active[u] && kuhn(mt[u])) { mt[u] = v; return 1; }
    return 0;
}

inline void solve () {
    int n, m, k; cin >> n >> m >> k;
    for (int i = 0; i < n; ++i) {
        int u, v; cin >> u >> v; --u, --v;
        g[v].pb(u);
    }

    fill(mt, mt + N, -1);
    vec <int> girls;
    for (int i = 0; i < m; ++i) girls.pb(i);

    ll ans = 0;
    for (int l = 0, r = 0; l < n; ++l) {
        while (r < n) {
            active[r] = 1;
            while (sz(girls)) {
                ++us;
                int go = girls.back();
                if (kuhn(go)) girls.pop_back();
                else break;
            }
            if (!sz(girls)) break;
            ++r;
        }

        if (sz(girls)) continue;

        ans += n - r + 1;
        if (~mt[l]) {
            girls.pb(mt[l]);
            mt[l] = -1;
            active[l] = 0;
        }
    }
    cout << ans << endl;
}

signed main () {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif// LOCAL
    int t = 1; //cin >> t;
    while (t--) solve();
    return 0;
}

Subtask #1
14.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 1108 KB Output isn't correct
2 Incorrect 1 ms 1108 KB Output isn't correct
3 Incorrect 1 ms 1204 KB Output isn't correct
4 Incorrect 1 ms 1108 KB Output isn't correct
5 Incorrect 1 ms 1108 KB Output isn't correct
6 Incorrect 1 ms 1208 KB Output isn't correct
7 Incorrect 1 ms 1208 KB Output isn't correct
8 Incorrect 1 ms 1108 KB Output isn't correct
9 Correct 1 ms 1108 KB Output is correct
10 Correct 1 ms 1108 KB Output is correct
11 Incorrect 1 ms 1108 KB Output isn't correct
12 Correct 1 ms 1208 KB Output is correct
13 Incorrect 1 ms 1108 KB Output isn't correct
14 Incorrect 1 ms 1216 KB Output isn't correct
15 Incorrect 1 ms 1108 KB Output isn't correct
16 Incorrect 1 ms 1108 KB Output isn't correct
17 Incorrect 1 ms 1108 KB Output isn't correct
18 Incorrect 1 ms 1108 KB Output isn't correct
19 Incorrect 1 ms 1108 KB Output isn't correct
20 Incorrect 1 ms 1108 KB Output isn't correct
21 Correct 1 ms 1196 KB Output is correct
22 Incorrect 1 ms 1108 KB Output isn't correct
23 Incorrect 1 ms 1108 KB Output isn't correct
24 Incorrect 1 ms 1212 KB Output isn't correct
25 Incorrect 1 ms 1236 KB Output isn't correct
26 Incorrect 1 ms 1216 KB Output isn't correct
27 Correct 1 ms 1208 KB Output is correct
28 Incorrect 1 ms 1204 KB Output isn't correct
29 Incorrect 1 ms 1216 KB Output isn't correct
30 Incorrect 1 ms 1236 KB Output isn't correct
31 Incorrect 1 ms 1236 KB Output isn't correct
32 Incorrect 2 ms 1220 KB Output isn't correct
33 Correct 1 ms 1212 KB Output is correct
34 Incorrect 2 ms 1236 KB Output isn't correct
35 Incorrect 1 ms 1216 KB Output isn't correct
36 Incorrect 1 ms 1220 KB Output isn't correct
37 Incorrect 1 ms 1364 KB Output isn't correct
38 Incorrect 1 ms 1328 KB Output isn't correct
39 Incorrect 52 ms 1600 KB Output isn't correct
40 Correct 3 ms 1348 KB Output is correct
41 Incorrect 3 ms 1492 KB Output isn't correct
42 Incorrect 4 ms 1604 KB Output isn't correct
43 Incorrect 3 ms 1748 KB Output isn't correct
44 Incorrect 3 ms 1748 KB Output isn't correct
45 Incorrect 8 ms 1856 KB Output isn't correct
46 Incorrect 7 ms 2004 KB Output isn't correct
47 Incorrect 6 ms 2004 KB Output isn't correct
48 Incorrect 6 ms 1980 KB Output isn't correct
49 Incorrect 8 ms 2004 KB Output isn't correct
50 Runtime error 4 ms 3924 KB Execution killed with signal 11