Submission #526245

# Submission time Handle Problem Language Result Execution time Memory
526245 2022-02-14T03:47:16 Z armashka Marriage questions (IZhO14_marriage) C++17
40 / 100
1424 ms 3268 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) {
            if (q.front() < l) q.pop();
            if (q.empty()) break;
            if (dfs(q.front())) break;
            q.pop();
        }
        if (q.sz) 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")
      |
# 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 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 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 2 ms 1100 KB Output isn't correct
31 Incorrect 9 ms 1740 KB Output isn't correct
32 Incorrect 10 ms 1156 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 2252 KB Output isn't correct
36 Incorrect 11 ms 2180 KB Output isn't correct
37 Incorrect 31 ms 1836 KB Output isn't correct
38 Correct 58 ms 2576 KB Output is correct
39 Correct 25 ms 1296 KB Output is correct
40 Correct 19 ms 1356 KB Output is correct
41 Incorrect 36 ms 1532 KB Output isn't correct
42 Incorrect 82 ms 1824 KB Output isn't correct
43 Incorrect 108 ms 2036 KB Output isn't correct
44 Incorrect 257 ms 2528 KB Output isn't correct
45 Incorrect 49 ms 2104 KB Output isn't correct
46 Incorrect 997 ms 2932 KB Output isn't correct
47 Incorrect 409 ms 3128 KB Output isn't correct
48 Incorrect 491 ms 3040 KB Output isn't correct
49 Incorrect 1424 ms 3268 KB Output isn't correct
50 Correct 59 ms 1644 KB Output is correct