oj.uz

답안 #526236

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
526236 2022-02-14T03:18:46 Z armashka 결혼 문제 (IZhO14_marriage) C++17
48 / 100
 1500 ms 9908 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
#define fast ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define file(s) freopen(s".in", "r", stdin);freopen(s".out", "w", stdout);
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define pb push_back
#define sz size()
#define ft first
#define sd second
 
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef unsigned long long ull;
    
const int N = 2e5 + 10;
const int M = 1e3 + 5;
const ll inf = 2e18;
const ll mod = 1e9 + 7;
const double Pi = acos(-1); 
 
ll binpow(ll x, ll ti) { ll res = 1;while (ti){if(ti & 1)res *= x;x *= x;ti >>= 1; x %= mod; res %= mod;} return res;}
ll binmul(ll x, ll ti) { ll res = 0;while (ti){if(ti & 1)res += x;x += x;ti >>= 1; x %= mod; res %= mod;} return res;}
ll nok(ll a, ll b) { return (a*b)/__gcd(abs(a),abs(b)) * (a*b > 0 ? 1 : -1); }
bool odd(ll n) { return (n % 2 == 1); }                                   
bool even(ll n) { return (n % 2 == 0); }
 
ll n, m, k, a[N], b[N], mt[N], ans;
vector <ll> g[N];
bool used[N];
 
bool dfs(ll v, ll l, ll r) {
    if (v < l || r < v) return 0;
    used[v] = 1;
    for (auto to : g[v]) {
        if (mt[to] == -1) {
            mt[to] = v;
            return 1;
        }
    }
    for (auto to : g[v]) {
        if (!used[mt[to]] && dfs(mt[to], l, r)) {
            mt[to] = v;
            return 1;
        }
    }
    return 0;
}
 
bool check(ll l, ll r) {
    memset(mt, -1, sizeof(mt));
    for (int i = l; i <= r; ++ i) {
        memset(used, 0, sizeof(used));
        dfs(i, l, r);
    }
    for (int i = 1; i <= m; ++ i) {
        if (mt[i] == -1) return 0;
    }
    return 1;
}
 
const void solve(/*Armashka*/) {
    cin >> n >> m >> k;
    for (int i = 1; i <= k; ++ i) cin >> a[i] >> b[i], g[a[i]].pb(b[i]);
    for (int i = 1; i <= n; ++ i) {
        int l = 1, r = n - i + 1, j = -1;
        while (l <= r) {
            ll mid = (l + r) / 2;
            if (check(i, i + mid - 1)) r = mid - 1, j = i + mid - 1; 
            else l = mid + 1;
        }
        if (j == -1) continue;
        ans += n - j + 1;
    }
    cout << ans;
}  
 
signed main() {
    srand(time(NULL));
    fast;
    // file("");
    int tt = 1;
    // cin >> tt;
    while (tt --) {                                                             
        solve();
    }                            
}
// Uaqyt, otedi, ketedi, mulde bilinbei, ulger
// Kunder seni kutpeidi, susyz ospeidi gulder

Compilation message

marriage.cpp:5: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    5 | #pragma comment(linker, "/stack:200000000")
      |

Subtask #1
48.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 6732 KB Output is correct
2 Correct 4 ms 6732 KB Output is correct
3 Correct 4 ms 6732 KB Output is correct
4 Correct 4 ms 6732 KB Output is correct
5 Correct 4 ms 6732 KB Output is correct
6 Correct 4 ms 6732 KB Output is correct
7 Correct 8 ms 6776 KB Output is correct
8 Correct 3 ms 6732 KB Output is correct
9 Correct 4 ms 6740 KB Output is correct
10 Correct 3 ms 6732 KB Output is correct
11 Correct 3 ms 6732 KB Output is correct
12 Correct 4 ms 6732 KB Output is correct
13 Correct 4 ms 6732 KB Output is correct
14 Correct 8 ms 6732 KB Output is correct
15 Correct 8 ms 6732 KB Output is correct
16 Correct 11 ms 6772 KB Output is correct
17 Correct 9 ms 6732 KB Output is correct
18 Correct 9 ms 6780 KB Output is correct
19 Correct 121 ms 6860 KB Output is correct
20 Correct 120 ms 6780 KB Output is correct
21 Correct 143 ms 6764 KB Output is correct
22 Correct 145 ms 6768 KB Output is correct
23 Correct 127 ms 6732 KB Output is correct
24 Correct 127 ms 6732 KB Output is correct
25 Execution timed out 1585 ms 7116 KB Time limit exceeded
26 Execution timed out 1586 ms 6860 KB Time limit exceeded
27 Execution timed out 1586 ms 6732 KB Time limit exceeded
28 Execution timed out 1587 ms 6732 KB Time limit exceeded
29 Execution timed out 1593 ms 6988 KB Time limit exceeded
30 Execution timed out 1584 ms 6988 KB Time limit exceeded
31 Execution timed out 1574 ms 8144 KB Time limit exceeded
32 Execution timed out 1588 ms 6860 KB Time limit exceeded
33 Execution timed out 1592 ms 6732 KB Time limit exceeded
34 Execution timed out 1578 ms 6732 KB Time limit exceeded
35 Execution timed out 1585 ms 9420 KB Time limit exceeded
36 Execution timed out 1597 ms 9100 KB Time limit exceeded
37 Execution timed out 1590 ms 8268 KB Time limit exceeded
38 Execution timed out 1592 ms 9804 KB Time limit exceeded
39 Execution timed out 1589 ms 7020 KB Time limit exceeded
40 Execution timed out 1600 ms 7116 KB Time limit exceeded
41 Execution timed out 1593 ms 7372 KB Time limit exceeded
42 Execution timed out 1600 ms 7628 KB Time limit exceeded
43 Execution timed out 1598 ms 8212 KB Time limit exceeded
44 Execution timed out 1590 ms 9328 KB Time limit exceeded
45 Execution timed out 1588 ms 7884 KB Time limit exceeded
46 Execution timed out 1593 ms 9544 KB Time limit exceeded
47 Execution timed out 1552 ms 9692 KB Time limit exceeded
48 Execution timed out 1580 ms 9744 KB Time limit exceeded
49 Execution timed out 1600 ms 9908 KB Time limit exceeded
50 Execution timed out 1585 ms 7028 KB Time limit exceeded