oj.uz

답안 #1088806

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1088806 2024-09-15T06:35:10 Z KasymK 결혼 문제 (IZhO14_marriage) C++17
54 / 100
 1500 ms 5936 KB 
#include "bits/stdc++.h"
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#pragma GCC optimization ("03")
#pragma GCC optimization ("unroll-loops")
using namespace std;
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define tr(i, c) for(auto i = c.begin(); i != c.end(); ++i)
#define wr puts("----------------")
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
const int N = 1e5+5;
pii p[N];
int ed[N], st[N], n, m, k, love[N];
bool vis[N];
vector<pii> v;
vector<int> adj[N];
 
bool check(){
    set<int> st;
    for(auto &i : v)
        st.insert(i.ss);
    return ((int)st.size() == m);
}
 
bool kuhn(int x){
    if(vis[x])
        return 0;
    vis[x] = 1;
    for(auto i : adj[x])
        if(love[i] == -1 or kuhn(love[i])){
            love[i] = x;
            return 1;
        }
    return 0;
}
 
int main(){
    // freopen("file.in", "r", stdin);
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 1; i <= k; ++i){
        int a, b;
        scanf("%d%d", &a, &b);
        p[i].ff = a, p[i].ss = b;
    }
    sort(p+1, p+k+1);
    int _ = -1;
    for(int i = 1; i <= k; ++i){
        ed[p[i].ff] = i;
        if(p[i].ff != _)
            st[p[i].ff] = i;
        _ = p[i].ff;
    }
    for(int i = 1; i <= n; ++i)
        if (!ed[i])
            ed[i] = ed[i-1];
    st[n+1] = k+1;
    for(int i = n; i >= 1; i--)
        if (!st[i])
            st[i] = st[i+1];
    int answer = 0;
    for(int l = 1; l <= n; ++l)
        for(int r = l; r <= n; ++r){
            v.clear();
            for(int j = st[l]; j <= ed[r]; ++j)
                v.pb(p[j]);
            if(!check())
                continue;
            for(auto &i : v)
                adj[i.ff].pb(i.ss);
            for(int i = 1; i <= m; ++i)
                love[i] = -1;
            for(int i = l; i <= r; ++i){
                for(int j = l; j <= r; ++j)
                    vis[j] = 0;
                kuhn(i);
            }
            bool ok = 1;
            for(int i = 1; i <= m and ok; ++i)
                ok &= (love[i] != -1);
            for(int i = l; i <= r; ++i)
                adj[i].clear();
            if(ok){
                answer += n-r+1;
                break;
            }
        }
    printf("%d\n", answer);
    return 0;
}

Compilation message

marriage.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("03")
      | 
marriage.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("unroll-loops")
      | 
marriage.cpp: In function 'int main()':
marriage.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     scanf("%d%d%d", &n, &m, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
marriage.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |         scanf("%d%d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
54.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2780 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2648 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 1 ms 2652 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 1 ms 2652 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 2 ms 2652 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 46 ms 2652 KB Output is correct
20 Correct 17 ms 2652 KB Output is correct
21 Correct 7 ms 2652 KB Output is correct
22 Correct 5 ms 2904 KB Output is correct
23 Correct 18 ms 2904 KB Output is correct
24 Correct 14 ms 2904 KB Output is correct
25 Execution timed out 1596 ms 3028 KB Time limit exceeded
26 Correct 297 ms 2844 KB Output is correct
27 Correct 418 ms 2800 KB Output is correct
28 Correct 106 ms 2652 KB Output is correct
29 Execution timed out 1571 ms 3164 KB Time limit exceeded
30 Execution timed out 1566 ms 2908 KB Time limit exceeded
31 Execution timed out 1552 ms 3892 KB Time limit exceeded
32 Execution timed out 1555 ms 2904 KB Time limit exceeded
33 Execution timed out 1531 ms 2648 KB Time limit exceeded
34 Execution timed out 1517 ms 2648 KB Time limit exceeded
35 Execution timed out 1527 ms 5292 KB Time limit exceeded
36 Execution timed out 1534 ms 5328 KB Time limit exceeded
37 Execution timed out 1502 ms 3920 KB Time limit exceeded
38 Execution timed out 1550 ms 5936 KB Time limit exceeded
39 Execution timed out 1545 ms 3016 KB Time limit exceeded
40 Execution timed out 1563 ms 3152 KB Time limit exceeded
41 Execution timed out 1513 ms 3372 KB Time limit exceeded
42 Execution timed out 1598 ms 3664 KB Time limit exceeded
43 Execution timed out 1527 ms 4048 KB Time limit exceeded
44 Execution timed out 1522 ms 5068 KB Time limit exceeded
45 Execution timed out 1570 ms 3652 KB Time limit exceeded
46 Execution timed out 1570 ms 4696 KB Time limit exceeded
47 Execution timed out 1546 ms 5068 KB Time limit exceeded
48 Execution timed out 1558 ms 4916 KB Time limit exceeded
49 Execution timed out 1573 ms 4948 KB Time limit exceeded
50 Execution timed out 1564 ms 3156 KB Time limit exceeded