oj.uz

답안 #526240

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
526240 2022-02-14T03:36:47 Z armashka 결혼 문제 (IZhO14_marriage) C++17
38 / 100
 1325 ms 3432 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 && q.front() < l) q.pop();
        }
        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
38.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 2 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 10 ms 1644 KB Output isn't correct
32 Incorrect 10 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 14 ms 2252 KB Output isn't correct
36 Incorrect 12 ms 2136 KB Output isn't correct
37 Incorrect 31 ms 1740 KB Output isn't correct
38 Incorrect 55 ms 2548 KB Output isn't correct
39 Correct 17 ms 1332 KB Output is correct
40 Correct 16 ms 1420 KB Output is correct
41 Incorrect 29 ms 1584 KB Output isn't correct
42 Incorrect 85 ms 1964 KB Output isn't correct
43 Incorrect 113 ms 1992 KB Output isn't correct
44 Incorrect 258 ms 2528 KB Output isn't correct
45 Incorrect 47 ms 2104 KB Output isn't correct
46 Incorrect 959 ms 3112 KB Output isn't correct
47 Incorrect 427 ms 3152 KB Output isn't correct
48 Incorrect 418 ms 2992 KB Output isn't correct
49 Incorrect 1325 ms 3432 KB Output isn't correct
50 Correct 52 ms 1532 KB Output is correct