oj.uz

Submission #1088660

# Submission time Handle Problem Language Result Execution time Memory
1088660 2024-09-14T18:16:29 Z Kerim Marriage questions (IZhO14_marriage) C++17
66 / 100
 1500 ms 4888 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 n, m, k, love[N];
bool vis[N];
int l, r;
vector<int> g[N];

bool kuhn(int x){
    if(vis[x]) 
        return 0;
    vis[x] = 1;
    for(auto i : g[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);
    }
    ll answer = 0;
    for(l = 1; l <= n; ++l){
        if (r < l) r = l;
        vector<int> v;
        while (r <= n){
            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; i++)
            	ok &= (love[i] != -1);
            if (ok){
                answer += n-r+1;
                break;
            }
            r += 1;
        }
    }
    printf("%lld\n", answer);
    return 0;
}

Compilation message

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

Subtask #1
66.0 / 100.0

# Verdict Execution time Memory 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 2 ms 2788 KB Output is 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 2652 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 2 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 1 ms 2652 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 2 ms 2908 KB Output is correct
20 Correct 2 ms 2652 KB Output is correct
21 Correct 1 ms 2792 KB Output is correct
22 Correct 2 ms 2648 KB Output is correct
23 Correct 2 ms 2652 KB Output is correct
24 Correct 2 ms 2652 KB Output is correct
25 Correct 11 ms 2892 KB Output is correct
26 Correct 20 ms 2652 KB Output is correct
27 Correct 4 ms 2652 KB Output is correct
28 Correct 12 ms 2804 KB Output is correct
29 Correct 177 ms 2908 KB Output is correct
30 Correct 158 ms 2652 KB Output is correct
31 Correct 295 ms 3416 KB Output is correct
32 Execution timed out 1567 ms 2884 KB Time limit exceeded
33 Correct 10 ms 2652 KB Output is correct
34 Correct 430 ms 2832 KB Output is correct
35 Execution timed out 1539 ms 3928 KB Time limit exceeded
36 Execution timed out 1572 ms 3932 KB Time limit exceeded
37 Execution timed out 1534 ms 3632 KB Time limit exceeded
38 Execution timed out 1545 ms 4188 KB Time limit exceeded
39 Execution timed out 1542 ms 2884 KB Time limit exceeded
40 Execution timed out 1569 ms 2908 KB Time limit exceeded
41 Execution timed out 1555 ms 3060 KB Time limit exceeded
42 Execution timed out 1547 ms 3416 KB Time limit exceeded
43 Execution timed out 1507 ms 3672 KB Time limit exceeded
44 Execution timed out 1555 ms 4188 KB Time limit exceeded
45 Execution timed out 1536 ms 3672 KB Time limit exceeded
46 Execution timed out 1511 ms 4692 KB Time limit exceeded
47 Execution timed out 1565 ms 4444 KB Time limit exceeded
48 Execution timed out 1503 ms 4440 KB Time limit exceeded
49 Execution timed out 1525 ms 4888 KB Time limit exceeded
50 Execution timed out 1565 ms 2908 KB Time limit exceeded