oj.uz

답안 #526243

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
526243 2022-02-14T03:44:38 Z armashka 결혼 문제 (IZhO14_marriage) C++17
40 / 100
 1500 ms 4164 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) {
    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])) {
            mt[to] = v;
            return 1;
        }
    }
    return 0;
}

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]);
    int r = 1;
    for (int i = 1; i <= n; ++ i) mt[i] = -1;
    set <ll> q;
    for (int l = 1; l <= n; ++ l) {
        if (l > 1) {
            for (int i = 1; i <= m; ++ i) {
                if (mt[i] == l - 1) mt[i] = -1;
            }
            while (q.sz && *q.begin() < l) q.erase(q.begin());
        }
        set <ll> qq;
        while (q.sz && !dfs(*q.begin())) qq.insert(*q.begin()), q.erase(q.begin());
        if (q.sz) q.erase(q.begin());
        while (qq.sz) q.insert(*qq.begin()), qq.erase(qq.begin());
        r = max(r, l);
        while (r <= n) {
            ++ cnt;
            if (!dfs(r)) q.insert(r);
            bool ok = 1;
            for (int i = 1; i <= m; ++ i) {
                if (mt[i] == -1) ok = 0;
            }
            if (ok) break;
            ++ r;
        }
        ans += n - r + 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
40.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 972 KB Output isn't correct
2 Correct 1 ms 972 KB Output is correct
3 Incorrect 1 ms 972 KB Output isn't 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 Incorrect 1 ms 972 KB Output isn't correct
8 Correct 1 ms 972 KB Output is correct
9 Correct 1 ms 972 KB Output is correct
10 Incorrect 1 ms 972 KB Output isn't 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 Incorrect 1 ms 972 KB Output isn't correct
15 Incorrect 1 ms 972 KB Output isn't correct
16 Correct 1 ms 972 KB Output is correct
17 Incorrect 1 ms 972 KB Output isn't correct
18 Incorrect 1 ms 972 KB Output isn't correct
19 Incorrect 1 ms 972 KB Output isn't correct
20 Incorrect 1 ms 972 KB Output isn't correct
21 Correct 1 ms 972 KB Output is correct
22 Correct 1 ms 972 KB Output is correct
23 Incorrect 1 ms 1060 KB Output isn't correct
24 Incorrect 1 ms 972 KB Output isn't correct
25 Incorrect 3 ms 1228 KB Output isn't correct
26 Incorrect 4 ms 1096 KB Output isn't correct
27 Correct 11 ms 1068 KB Output is correct
28 Correct 12 ms 1052 KB Output is correct
29 Correct 10 ms 1204 KB Output is correct
30 Correct 10 ms 1100 KB Output is correct
31 Incorrect 10 ms 1748 KB Output isn't correct
32 Correct 23 ms 1164 KB Output is correct
33 Correct 60 ms 972 KB Output is correct
34 Correct 36 ms 1100 KB Output is correct
35 Incorrect 58 ms 2352 KB Output isn't correct
36 Incorrect 59 ms 2144 KB Output isn't correct
37 Incorrect 53 ms 1728 KB Output isn't correct
38 Correct 410 ms 2656 KB Output is correct
39 Execution timed out 1585 ms 1484 KB Time limit exceeded
40 Execution timed out 1582 ms 1612 KB Time limit exceeded
41 Execution timed out 1558 ms 1940 KB Time limit exceeded
42 Execution timed out 1592 ms 2380 KB Time limit exceeded
43 Execution timed out 1583 ms 2628 KB Time limit exceeded
44 Execution timed out 1586 ms 2960 KB Time limit exceeded
45 Execution timed out 1591 ms 2672 KB Time limit exceeded
46 Execution timed out 1597 ms 3068 KB Time limit exceeded
47 Execution timed out 1555 ms 4164 KB Time limit exceeded
48 Execution timed out 1585 ms 4100 KB Time limit exceeded
49 Execution timed out 1594 ms 3304 KB Time limit exceeded
50 Execution timed out 1579 ms 1952 KB Time limit exceeded