oj.uz

답안 #345368

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
345368 2021-01-07T08:01:55 Z vonatlus 결혼 문제 (IZhO14_marriage) C++14
34 / 100
 1500 ms 4732 KB 
/// wa 

#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:36777216")

#include<bits/stdc++.h>

#define x first
#define y second
#define pb push_back
#define sz(x) (int) x.size()
#define all(z) (z).begin(), (z).end()
 
using namespace std;

using ll = long long;
using pii = pair<int, int>;                                   

const int MOD = 1e9 + 7; 
const int INF = 1e9 + 1e2;
  
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void fin() {
#ifdef AM
    freopen(".in", "r", stdin);
#endif        
}                   

const bool flag = 0;

const int N = 5e4+10;

int was[N];

int mt[N], p[N], tmp;

vector<int> adj[N], g[N];
                     
bool dfs(int x) {
    if (was[x] == tmp) return 0;
    was[x] = tmp;
    for (int to : adj[x]) {
        if (mt[to] == -1) {
            mt[to] = x;
            p[x] = to;
            return 1;
        }
    }
    for (int to : adj[x]) {
        if (dfs(to)) {
            mt[to] = x;
            p[x] = to;
            return 1;
        }
    }
    return 0;
}

int n, m, k;

bool check(int l, int r) {
    for (int i = l; i <= r; ++i) {
        for (int to : g[i]) {
            adj[to].pb(i);
        }
    }
    fill(p, p+m, -1);
    for (int i = 0; i < m; ++i) {
        tmp++;
        dfs(i);
    }
    int ok = 1;
    for (int i = 0; i < m; ++i) {
        if (~p[i]) {
            mt[p[i]] = -1;
        } else {          
            ok = 0;
        }
    }
    for (int i = l; i <= r; ++i) {
        for (int to : g[i]) {
            adj[to].pop_back();
        }
    }
    return ok;
}

void ma1n() {
    cin >> n >> m >> k;
    for (int u, v; k--;) {
        cin >> u >> v;
        u--, v--;
        g[u].pb(v);
    }
    ll ans = 0;
    memset(mt, -1, sizeof(mt));
    for (int i = 0; i < n; ++i) {
        int l = i+m-1;
        int r = n;
        int j = -1;
        while (l <= r) {
            int mid = l+r >> 1;
            if (check(i, mid)) {
                j = mid, r = mid-1;        
            } else {
                l = mid+1;
            }
        }
        if (~j) {
            ans += n-j;
        }
    }
    cout << ans;
} 

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr), fin();
    int ts = 1;
    if (flag) {
        cin >> ts;
    }
    while (ts--) {
        ma1n(); 
    }
    return 0;
}

Compilation message

marriage.cpp: In function 'void ma1n()':
marriage.cpp:103:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  103 |             int mid = l+r >> 1;
      |                       ~^~

Subtask #1
34.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 3072 KB Output isn't correct
2 Incorrect 2 ms 2924 KB Output isn't correct
3 Incorrect 2 ms 2924 KB Output isn't correct
4 Incorrect 2 ms 2972 KB Output isn't correct
5 Correct 3 ms 2924 KB Output is correct
6 Correct 3 ms 2924 KB Output is correct
7 Incorrect 2 ms 2924 KB Output isn't correct
8 Correct 2 ms 2924 KB Output is correct
9 Correct 3 ms 2924 KB Output is correct
10 Correct 2 ms 2924 KB Output is correct
11 Correct 2 ms 2924 KB Output is correct
12 Correct 3 ms 2828 KB Output is correct
13 Correct 2 ms 2924 KB Output is correct
14 Incorrect 2 ms 2944 KB Output isn't correct
15 Incorrect 3 ms 2924 KB Output isn't correct
16 Incorrect 3 ms 2924 KB Output isn't correct
17 Correct 4 ms 2924 KB Output is correct
18 Correct 2 ms 2924 KB Output is correct
19 Incorrect 46 ms 2996 KB Output isn't correct
20 Incorrect 19 ms 2924 KB Output isn't correct
21 Correct 4 ms 2924 KB Output is correct
22 Incorrect 4 ms 2924 KB Output isn't correct
23 Correct 5 ms 2964 KB Output is correct
24 Correct 4 ms 2924 KB Output is correct
25 Execution timed out 1577 ms 3076 KB Time limit exceeded
26 Incorrect 423 ms 3000 KB Output isn't correct
27 Correct 23 ms 2924 KB Output is correct
28 Incorrect 12 ms 2952 KB Output isn't correct
29 Correct 217 ms 3056 KB Output is correct
30 Correct 190 ms 3060 KB Output is correct
31 Execution timed out 1531 ms 3564 KB Time limit exceeded
32 Execution timed out 1556 ms 3052 KB Time limit exceeded
33 Correct 65 ms 2928 KB Output is correct
34 Incorrect 76 ms 2980 KB Output isn't correct
35 Execution timed out 1583 ms 3948 KB Time limit exceeded
36 Execution timed out 1544 ms 3948 KB Time limit exceeded
37 Execution timed out 1557 ms 3596 KB Time limit exceeded
38 Execution timed out 1574 ms 4204 KB Time limit exceeded
39 Execution timed out 1585 ms 3052 KB Time limit exceeded
40 Execution timed out 1582 ms 3180 KB Time limit exceeded
41 Execution timed out 1505 ms 3500 KB Time limit exceeded
42 Execution timed out 1559 ms 3436 KB Time limit exceeded
43 Execution timed out 1571 ms 3564 KB Time limit exceeded
44 Execution timed out 1596 ms 4076 KB Time limit exceeded
45 Execution timed out 1570 ms 3748 KB Time limit exceeded
46 Execution timed out 1524 ms 4732 KB Time limit exceeded
47 Execution timed out 1535 ms 4336 KB Time limit exceeded
48 Execution timed out 1548 ms 4332 KB Time limit exceeded
49 Execution timed out 1561 ms 4332 KB Time limit exceeded
50 Execution timed out 1571 ms 3052 KB Time limit exceeded