oj.uz

답안 #1088024

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1088024 2024-09-13T18:05:08 Z Kerim 결혼 문제 (IZhO14_marriage) C++17
26 / 100
 1500 ms 13732 KB 
#include "bits/stdc++.h"
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;
    }
    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;
            // .ff = men, .ss = women
            for(auto &i : v)
                adj[i.ff].pb(i.ss);
            // for(int x = l; x <= r; ++x){
            //     printf("%d: ", x);
            //     for(auto i : adj[x])
            //         printf("%d ", i);
            //     puts("");
            // }
            for (int j = 1; j <= m; j++)
            	love[j] = -1;
            for (int i = l; i <= r; i++){
            	for (int j = 1; j <= n; j++)
            		vis[j] = 0;
            	kuhn(i);
            }
            bool ok = 1;
            for (int i = 1; i <= m and ok; i++)
            	ok &= (love[i] != -1);
            answer += ok;
            // wr;
            for(int i = l; i <= r; ++i)
                adj[i].clear();
        }
    printf("%d\n", answer);
    return 0;
}

Compilation message

marriage.cpp: In function 'int main()':
marriage.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     scanf("%d%d%d", &n, &m, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
marriage.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |         scanf("%d%d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
26.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Incorrect 1 ms 2652 KB Output isn't correct
3 Incorrect 1 ms 2652 KB Output isn't correct
4 Incorrect 1 ms 2652 KB Output isn't correct
5 Incorrect 1 ms 2652 KB Output isn't correct
6 Incorrect 1 ms 2652 KB Output isn't correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2796 KB Output is correct
11 Correct 1 ms 2820 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Incorrect 1 ms 2796 KB Output isn't correct
14 Incorrect 1 ms 2792 KB Output isn't correct
15 Correct 1 ms 2652 KB Output is correct
16 Incorrect 1 ms 2652 KB Output isn't correct
17 Incorrect 1 ms 2652 KB Output isn't correct
18 Incorrect 1 ms 2816 KB Output isn't correct
19 Correct 131 ms 2652 KB Output is correct
20 Correct 34 ms 2652 KB Output is correct
21 Correct 6 ms 2652 KB Output is correct
22 Incorrect 5 ms 2652 KB Output isn't correct
23 Incorrect 19 ms 2652 KB Output isn't correct
24 Incorrect 13 ms 2836 KB Output isn't correct
25 Execution timed out 1598 ms 3156 KB Time limit exceeded
26 Execution timed out 1557 ms 2652 KB Time limit exceeded
27 Correct 383 ms 13732 KB Output is correct
28 Incorrect 68 ms 2808 KB Output isn't correct
29 Execution timed out 1547 ms 3148 KB Time limit exceeded
30 Execution timed out 1511 ms 3028 KB Time limit exceeded
31 Execution timed out 1567 ms 3936 KB Time limit exceeded
32 Execution timed out 1535 ms 2904 KB Time limit exceeded
33 Correct 1437 ms 2652 KB Output is correct
34 Execution timed out 1566 ms 2652 KB Time limit exceeded
35 Execution timed out 1539 ms 5572 KB Time limit exceeded
36 Execution timed out 1529 ms 5040 KB Time limit exceeded
37 Execution timed out 1549 ms 3964 KB Time limit exceeded
38 Execution timed out 1526 ms 5932 KB Time limit exceeded
39 Execution timed out 1561 ms 3180 KB Time limit exceeded
40 Execution timed out 1541 ms 3412 KB Time limit exceeded
41 Execution timed out 1566 ms 3248 KB Time limit exceeded
42 Execution timed out 1552 ms 3728 KB Time limit exceeded
43 Execution timed out 1560 ms 4096 KB Time limit exceeded
44 Execution timed out 1580 ms 5072 KB Time limit exceeded
45 Execution timed out 1529 ms 3576 KB Time limit exceeded
46 Execution timed out 1535 ms 4944 KB Time limit exceeded
47 Execution timed out 1595 ms 5360 KB Time limit exceeded
48 Execution timed out 1542 ms 4944 KB Time limit exceeded
49 Execution timed out 1573 ms 5072 KB Time limit exceeded
50 Execution timed out 1537 ms 3152 KB Time limit exceeded