oj.uz

Submission #526238

# Submission time Handle Problem Language Result Execution time Memory
526238 2022-02-14T03:31:01 Z armashka Marriage questions (IZhO14_marriage) C++17
40 / 100
 1182 ms 3144 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;
    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;
            }
        }
        r = max(r, l);
        while (r <= n) {
            ++ cnt;
            dfs(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

# 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 1012 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 972 KB Output isn't correct
24 Incorrect 1 ms 972 KB Output isn't correct
25 Incorrect 5 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 2 ms 1100 KB Output isn't correct
31 Incorrect 10 ms 1740 KB Output isn't correct
32 Incorrect 9 ms 1156 KB Output isn't correct
33 Correct 1 ms 972 KB Output is correct
34 Correct 2 ms 1100 KB Output is correct
35 Incorrect 13 ms 2252 KB Output isn't correct
36 Incorrect 12 ms 2136 KB Output isn't correct
37 Incorrect 35 ms 1840 KB Output isn't correct
38 Correct 52 ms 2572 KB Output is correct
39 Correct 18 ms 1228 KB Output is correct
40 Correct 18 ms 1352 KB Output is correct
41 Incorrect 26 ms 1484 KB Output isn't correct
42 Incorrect 83 ms 1732 KB Output isn't correct
43 Incorrect 104 ms 1864 KB Output isn't correct
44 Incorrect 282 ms 2484 KB Output isn't correct
45 Incorrect 49 ms 1924 KB Output isn't correct
46 Incorrect 896 ms 3084 KB Output isn't correct
47 Incorrect 432 ms 2884 KB Output isn't correct
48 Incorrect 440 ms 2884 KB Output isn't correct
49 Incorrect 1182 ms 3144 KB Output isn't correct
50 Correct 51 ms 1408 KB Output is correct