oj.uz

답안 #526244

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
526244 2022-02-14T03:46:33 Z armashka 결혼 문제 (IZhO14_marriage) C++17
38 / 100
 1315 ms 3228 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 (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")
      |

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 Runtime error 1 ms 1868 KB Execution killed with signal 11
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 2 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 8 ms 1712 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 2 ms 1100 KB Output is correct
35 Incorrect 14 ms 2288 KB Output isn't correct
36 Incorrect 12 ms 2232 KB Output isn't correct
37 Incorrect 32 ms 1824 KB Output isn't correct
38 Correct 62 ms 2568 KB Output is correct
39 Correct 18 ms 1336 KB Output is correct
40 Correct 16 ms 1412 KB Output is correct
41 Incorrect 29 ms 1520 KB Output isn't correct
42 Incorrect 85 ms 1860 KB Output isn't correct
43 Incorrect 105 ms 1988 KB Output isn't correct
44 Incorrect 269 ms 2488 KB Output isn't correct
45 Incorrect 47 ms 2108 KB Output isn't correct
46 Incorrect 968 ms 3136 KB Output isn't correct
47 Incorrect 403 ms 3012 KB Output isn't correct
48 Incorrect 418 ms 3148 KB Output isn't correct
49 Incorrect 1315 ms 3228 KB Output isn't correct
50 Correct 51 ms 1484 KB Output is correct