답안 #526237

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
526237 2022-02-14T03:21:44 Z armashka 결혼 문제 (IZhO14_marriage) C++17
62 / 100
1500 ms 3008 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 = 1e5 + 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); }
 
int n, m, k, a[N], b[N], mt[2005], ans, used[30005], cnt;
vector <int> g[30005];
 
bool dfs(int v, int l, int r) {
    if (v < l || r < v) return 0;
    used[v] = cnt;
    for (auto to : g[v]) {
        if (mt[to] == -1) {
            mt[to] = v;
            return 1;
        }
    }
    for (auto to : g[v]) {
        if (used[mt[to]] < cnt && dfs(mt[to], l, r)) {
            mt[to] = v;
            return 1;
        }
    }
    return 0;
}
 
bool check(int l, int r) {
    memset(mt, -1, sizeof(mt));
    cnt = 0;
    for (int i = l; i <= r; ++ i) {
        ++ cnt;
        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) {
            int 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")
      |
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 972 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 1 ms 972 KB Output is correct
4 Correct 1 ms 972 KB Output is correct
5 Correct 1 ms 972 KB Output is correct
6 Correct 1 ms 972 KB Output is correct
7 Correct 1 ms 972 KB Output is correct
8 Correct 1 ms 972 KB Output is correct
9 Correct 1 ms 972 KB Output is correct
10 Correct 1 ms 972 KB Output is correct
11 Correct 1 ms 972 KB Output is correct
12 Correct 1 ms 972 KB Output is correct
13 Correct 1 ms 972 KB Output is correct
14 Correct 1 ms 972 KB Output is correct
15 Correct 1 ms 972 KB Output is correct
16 Correct 1 ms 972 KB Output is correct
17 Correct 1 ms 972 KB Output is correct
18 Correct 1 ms 972 KB Output is correct
19 Correct 3 ms 972 KB Output is correct
20 Correct 2 ms 972 KB Output is correct
21 Correct 1 ms 972 KB Output is correct
22 Correct 1 ms 972 KB Output is correct
23 Correct 2 ms 972 KB Output is correct
24 Correct 1 ms 972 KB Output is correct
25 Correct 225 ms 1228 KB Output is correct
26 Correct 164 ms 972 KB Output is correct
27 Correct 24 ms 972 KB Output is correct
28 Correct 6 ms 972 KB Output is correct
29 Execution timed out 1588 ms 1100 KB Time limit exceeded
30 Correct 1471 ms 1152 KB Output is correct
31 Execution timed out 1585 ms 1740 KB Time limit exceeded
32 Execution timed out 1587 ms 1100 KB Time limit exceeded
33 Correct 40 ms 972 KB Output is correct
34 Correct 37 ms 1088 KB Output is correct
35 Execution timed out 1591 ms 2388 KB Time limit exceeded
36 Execution timed out 1583 ms 2124 KB Time limit exceeded
37 Execution timed out 1583 ms 1868 KB Time limit exceeded
38 Execution timed out 1591 ms 2508 KB Time limit exceeded
39 Execution timed out 1583 ms 1300 KB Time limit exceeded
40 Execution timed out 1582 ms 1228 KB Time limit exceeded
41 Execution timed out 1589 ms 1484 KB Time limit exceeded
42 Execution timed out 1594 ms 1780 KB Time limit exceeded
43 Execution timed out 1578 ms 1912 KB Time limit exceeded
44 Execution timed out 1593 ms 2372 KB Time limit exceeded
45 Execution timed out 1592 ms 1868 KB Time limit exceeded
46 Execution timed out 1577 ms 3008 KB Time limit exceeded
47 Execution timed out 1577 ms 2796 KB Time limit exceeded
48 Execution timed out 1581 ms 2800 KB Time limit exceeded
49 Execution timed out 1588 ms 2956 KB Time limit exceeded
50 Execution timed out 1556 ms 1356 KB Time limit exceeded