oj.uz

답안 #1088280

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1088280 2024-09-14T07:44:38 Z Kerim 결혼 문제 (IZhO14_marriage) C++17
14 / 100
 1500 ms 8024 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;
int ed[N], st[N], n, m, k, love[N];
bool vis[N], vis1[N], mark[N];
vector<int> adj[N], g[N];

bool check(vector<int> &v){
    int cnt = 0;
    for(auto &i : v)
        cnt += !mark[i], mark[i] = 1;
    for(auto &i : v)
        mark[i] = 0;
    return (cnt == 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);
        g[a].push_back(b);
    }
    int answer = 0;
    for(int l = 1; l <= n; ++l){
        vector<int> v;
        bool good = false;
        for(int r = l; r <= n; ++r){
            for(auto &i : g[r])
                v.pb(i);
            for(auto &i : g[r])
                adj[r].pb(i);
            if(good or !check(v))
                continue;
            good = true;
            for (int j = 1; j <= m; j++)
            	love[j] = -1;
            // Improved Kuhn starts here
            for (int j = l; j <= r; j++)
                vis1[j] = 0;
            for (int j = l; j <= r; j++)
                for (int to : adj[j])
                    if (love[to] == -1) {
                        love[to] = j;
                        vis1[j] = true;
                        break;
                    }
            for (int i = l; i <= r; i++){
                if (vis1[i])
                    continue;
                // Improved Kuhn ends here
            	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);
            answer += ok;
        }
        for (int i = 1; i <= n; i++)
            adj[i].clear();
    }
    printf("%d\n", answer);
    return 0;
}

Compilation message

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

Subtask #1
14.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 4956 KB Output isn't correct
2 Incorrect 2 ms 4956 KB Output isn't correct
3 Incorrect 2 ms 4956 KB Output isn't correct
4 Incorrect 2 ms 4956 KB Output isn't correct
5 Incorrect 2 ms 4956 KB Output isn't correct
6 Incorrect 2 ms 4956 KB Output isn't correct
7 Incorrect 2 ms 4956 KB Output isn't correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 2 ms 4956 KB Output is correct
10 Correct 2 ms 4956 KB Output is correct
11 Incorrect 2 ms 4956 KB Output isn't correct
12 Correct 2 ms 4956 KB Output is correct
13 Incorrect 2 ms 4952 KB Output isn't correct
14 Incorrect 2 ms 4956 KB Output isn't correct
15 Incorrect 2 ms 4956 KB Output isn't correct
16 Incorrect 2 ms 4932 KB Output isn't correct
17 Incorrect 2 ms 5132 KB Output isn't correct
18 Incorrect 2 ms 4956 KB Output isn't correct
19 Incorrect 3 ms 5212 KB Output isn't correct
20 Incorrect 2 ms 4956 KB Output isn't correct
21 Correct 3 ms 4956 KB Output is correct
22 Incorrect 3 ms 4956 KB Output isn't correct
23 Incorrect 6 ms 4956 KB Output isn't correct
24 Incorrect 4 ms 4956 KB Output isn't correct
25 Incorrect 18 ms 5208 KB Output isn't correct
26 Incorrect 28 ms 5228 KB Output isn't correct
27 Correct 35 ms 4956 KB Output is correct
28 Incorrect 9 ms 4952 KB Output isn't correct
29 Incorrect 514 ms 5212 KB Output isn't correct
30 Incorrect 452 ms 5208 KB Output isn't correct
31 Incorrect 278 ms 6192 KB Output isn't correct
32 Incorrect 1336 ms 5296 KB Output isn't correct
33 Correct 120 ms 4956 KB Output is correct
34 Incorrect 239 ms 5172 KB Output isn't correct
35 Execution timed out 1556 ms 7140 KB Time limit exceeded
36 Execution timed out 1558 ms 7080 KB Time limit exceeded
37 Execution timed out 1536 ms 6228 KB Time limit exceeded
38 Execution timed out 1541 ms 7536 KB Time limit exceeded
39 Execution timed out 1547 ms 5312 KB Time limit exceeded
40 Execution timed out 1561 ms 5572 KB Time limit exceeded
41 Execution timed out 1569 ms 5972 KB Time limit exceeded
42 Execution timed out 1528 ms 6104 KB Time limit exceeded
43 Execution timed out 1571 ms 6396 KB Time limit exceeded
44 Execution timed out 1545 ms 7020 KB Time limit exceeded
45 Execution timed out 1564 ms 6636 KB Time limit exceeded
46 Execution timed out 1572 ms 8024 KB Time limit exceeded
47 Execution timed out 1561 ms 7068 KB Time limit exceeded
48 Execution timed out 1571 ms 7168 KB Time limit exceeded
49 Execution timed out 1563 ms 7972 KB Time limit exceeded
50 Execution timed out 1559 ms 5212 KB Time limit exceeded