oj.uz

Submission #526239

# Submission time Handle Problem Language Result Execution time Memory
526239 2022-02-14T03:34:33 Z armashka Marriage questions (IZhO14_marriage) C++17
36 / 100
 1311 ms 3288 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;
    queue <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 && !dfs(q.front())) q.pop();
        r = max(r, l);
        while (r <= n) {
            ++ cnt;
            if (!dfs(r)) q.push(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
36.0 / 100.0

# Verdict Execution time Memory 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 Incorrect 1 ms 972 KB Output isn't 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 972 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 2 ms 972 KB Output isn't correct
27 Correct 1 ms 972 KB Output is correct
28 Correct 1 ms 972 KB Output is correct
29 Incorrect 3 ms 1100 KB Output isn't correct
30 Incorrect 3 ms 1100 KB Output isn't correct
31 Incorrect 9 ms 1740 KB Output isn't correct
32 Incorrect 9 ms 1100 KB Output isn't correct
33 Correct 1 ms 972 KB Output is correct
34 Correct 1 ms 1100 KB Output is correct
35 Incorrect 13 ms 2352 KB Output isn't correct
36 Incorrect 12 ms 2180 KB Output isn't correct
37 Incorrect 31 ms 1740 KB Output isn't correct
38 Incorrect 45 ms 2596 KB Output isn't correct
39 Correct 19 ms 1228 KB Output is correct
40 Correct 21 ms 1484 KB Output is correct
41 Incorrect 28 ms 1500 KB Output isn't correct
42 Incorrect 85 ms 1844 KB Output isn't correct
43 Incorrect 109 ms 1988 KB Output isn't correct
44 Incorrect 258 ms 2500 KB Output isn't correct
45 Incorrect 53 ms 2292 KB Output isn't correct
46 Incorrect 959 ms 2904 KB Output isn't correct
47 Incorrect 408 ms 3064 KB Output isn't correct
48 Incorrect 446 ms 3288 KB Output isn't correct
49 Incorrect 1311 ms 3268 KB Output isn't correct
50 Correct 50 ms 1484 KB Output is correct