oj.uz

Submission #91368

# Submission time Handle Problem Language Result Execution time Memory
91368 2018-12-27T09:16:27 Z mirbek01 Marriage questions (IZhO14_marriage) C++11
74 / 100
 1500 ms 14428 KB 
# include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 2;

int n, m, k, mt[N], used[N], ans, L, R;
vector <int> g[N], vr, mr;

bool dfs(int v){
      if(used[v])
            return 0;
      vr.push_back(v);
      used[v] = 1;
      for(int to : g[v]){
            if((to > R || to < L) && to <= n)
                  continue;
            if(mt[to] == -1 || dfs(mt[to])){
                  if(mt[to] == -1)
                        mr.push_back(to);
                  if(mt[v] == -1)
                        mr.push_back(v);
                  mt[to] = v;
                  mt[v] = to;
                  return true;
            }
      }
      return false;
}

bool check(){
      for(int i = 0; i < (int)mr.size(); i ++)
            mt[ mr[i] ] = -1;
      mr.clear();
      for(int i = n + 1; i <= n + m; i ++){
            for(int j = 0; j < (int)vr.size(); j ++){
                  used[ vr[j] ] = 0;
            }
            vr.clear();
            dfs(i);
      }
      for(int i = n + 1; i <= n + m; i ++){
            if(mt[i] == -1)
                  return false;
      }
      return true;
}

int main(){
      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 + n);
            g[b + n].push_back(a);
      }

      for(int i = 1; i <= n + m; i ++){
            sort(g[i].begin(), g[i].end());
      }

      memset(mt, -1, sizeof(mt));

      int pt = 1;

      for(int i = 1; i <= n - m + 1; i ++){
            int lo = 1, hi = i;
            L = i, R = pt;
            while(pt <= n && !check())
                  pt ++, R = pt;
            ans += n - pt + 1;
      }

      printf("%d", ans);
}

Compilation message

marriage.cpp: In function 'int main()':
marriage.cpp:68:17: warning: unused variable 'lo' [-Wunused-variable]
             int lo = 1, hi = i;
                 ^~
marriage.cpp:68:25: warning: unused variable 'hi' [-Wunused-variable]
             int lo = 1, hi = i;
                         ^~
marriage.cpp:50:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d %d", &n, &m, &k);
       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
marriage.cpp:54:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d", &a, &b);
             ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
74.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3064 KB Output is correct
2 Correct 4 ms 3064 KB Output is correct
3 Correct 4 ms 3104 KB Output is correct
4 Correct 4 ms 3124 KB Output is correct
5 Correct 4 ms 3128 KB Output is correct
6 Correct 4 ms 3336 KB Output is correct
7 Correct 4 ms 3336 KB Output is correct
8 Correct 4 ms 3336 KB Output is correct
9 Correct 4 ms 3336 KB Output is correct
10 Correct 4 ms 3428 KB Output is correct
11 Correct 4 ms 3428 KB Output is correct
12 Correct 4 ms 3428 KB Output is correct
13 Correct 4 ms 3428 KB Output is correct
14 Correct 4 ms 3428 KB Output is correct
15 Correct 4 ms 3428 KB Output is correct
16 Correct 4 ms 3428 KB Output is correct
17 Correct 4 ms 3428 KB Output is correct
18 Correct 4 ms 3428 KB Output is correct
19 Correct 17 ms 3440 KB Output is correct
20 Correct 7 ms 3440 KB Output is correct
21 Correct 4 ms 3440 KB Output is correct
22 Correct 5 ms 3440 KB Output is correct
23 Correct 10 ms 3440 KB Output is correct
24 Correct 9 ms 3484 KB Output is correct
25 Correct 458 ms 3680 KB Output is correct
26 Correct 62 ms 3680 KB Output is correct
27 Correct 5 ms 3680 KB Output is correct
28 Correct 30 ms 3680 KB Output is correct
29 Correct 18 ms 3680 KB Output is correct
30 Correct 14 ms 3748 KB Output is correct
31 Execution timed out 1579 ms 4896 KB Time limit exceeded
32 Correct 813 ms 4896 KB Output is correct
33 Correct 9 ms 4896 KB Output is correct
34 Correct 1104 ms 4896 KB Output is correct
35 Execution timed out 1577 ms 5896 KB Time limit exceeded
36 Execution timed out 1564 ms 6520 KB Time limit exceeded
37 Execution timed out 1581 ms 6892 KB Time limit exceeded
38 Execution timed out 1560 ms 8076 KB Time limit exceeded
39 Execution timed out 1544 ms 8076 KB Time limit exceeded
40 Correct 651 ms 8076 KB Output is correct
41 Execution timed out 1533 ms 8076 KB Time limit exceeded
42 Correct 587 ms 8076 KB Output is correct
43 Correct 782 ms 8512 KB Output is correct
44 Correct 1345 ms 9784 KB Output is correct
45 Execution timed out 1549 ms 9784 KB Time limit exceeded
46 Execution timed out 1550 ms 11380 KB Time limit exceeded
47 Execution timed out 1571 ms 12236 KB Time limit exceeded
48 Execution timed out 1549 ms 13232 KB Time limit exceeded
49 Execution timed out 1566 ms 14428 KB Time limit exceeded
50 Execution timed out 1552 ms 14428 KB Time limit exceeded