답안 #91382 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
91382	2018-12-27T09:39:12 Z	mirbek01	결혼 문제 (IZhO14_marriage)	C++11	66 / 100	1500 ms	13244 KB

marriage

# 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(){
      if(mt[L] == -1)
            return true;
      for(int i = n + 1; i <= n + m; i ++){
            if(mt[i] == -1){
                  if(!dfs(i)){
                        for(int j = 0; j < (int)vr.size(); j ++)
                              used[vr[j]] = 0;
                        return false;
                  }
                  for(int j = 0; j < (int)vr.size(); j ++)
                        used[vr[j]] = 0;
            }
      }
      return true;
}

bool ok(){
      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 lo = 1, hi = n, pos = -1;

      L = 1;

      while(hi - lo > 1){
            int md = (lo + hi) >> 1;
            R = md;
            if(ok())
                  hi = md - 1, pos = md;
            else
                  lo = md + 1;
      }

      if(pos == -1){
            cout << 0 << endl;
            return 0;
      }

      ans += n - pos + 1;

      if(mt[L] != -1){
            mt[mt[L]] = -1;
      }

      memset(used, 0, sizeof(used));

      int pt = pos;

      for(int i = 2; 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;
            if(mt[L] != -1){
                  mt[mt[L]] = -1;
            }
      }

      printf("%d", ans);
}

Compilation message

marriage.cpp: In function 'int main()':
marriage.cpp:111:17: warning: unused variable 'lo' [-Wunused-variable]
             int lo = 1, hi = i;
                 ^~
marriage.cpp:111:25: warning: unused variable 'hi' [-Wunused-variable]
             int lo = 1, hi = i;
                         ^~
marriage.cpp:67: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:71: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
66.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	3448 KB	Output is correct
2	Incorrect	4 ms	3584 KB	Output isn't correct
3	Correct	4 ms	3584 KB	Output is correct
4	Correct	4 ms	3684 KB	Output is correct
5	Correct	4 ms	3684 KB	Output is correct
6	Correct	4 ms	3684 KB	Output is correct
7	Correct	4 ms	3684 KB	Output is correct
8	Incorrect	4 ms	3684 KB	Output isn't correct
9	Correct	4 ms	3684 KB	Output is correct
10	Correct	4 ms	3684 KB	Output is correct
11	Incorrect	4 ms	3684 KB	Output isn't correct
12	Correct	4 ms	3684 KB	Output is correct
13	Incorrect	4 ms	3724 KB	Output isn't correct
14	Correct	4 ms	3728 KB	Output is correct
15	Incorrect	4 ms	3732 KB	Output isn't correct
16	Correct	4 ms	3736 KB	Output is correct
17	Correct	4 ms	3812 KB	Output is correct
18	Correct	4 ms	3812 KB	Output is correct
19	Correct	6 ms	3812 KB	Output is correct
20	Correct	5 ms	3812 KB	Output is correct
21	Correct	5 ms	3812 KB	Output is correct
22	Correct	4 ms	3812 KB	Output is correct
23	Correct	5 ms	3812 KB	Output is correct
24	Correct	5 ms	3812 KB	Output is correct
25	Incorrect	43 ms	4688 KB	Output isn't correct
26	Incorrect	16 ms	4688 KB	Output isn't correct
27	Correct	4 ms	4688 KB	Output is correct
28	Correct	6 ms	4688 KB	Output is correct
29	Correct	6 ms	4688 KB	Output is correct
30	Correct	7 ms	4688 KB	Output is correct
31	Correct	385 ms	6984 KB	Output is correct
32	Correct	14 ms	6984 KB	Output is correct
33	Correct	4 ms	6984 KB	Output is correct
34	Correct	27 ms	6984 KB	Output is correct
35	Correct	190 ms	6984 KB	Output is correct
36	Correct	140 ms	6984 KB	Output is correct
37	Execution timed out	1561 ms	13244 KB	Time limit exceeded
38	Correct	31 ms	13244 KB	Output is correct
39	Execution timed out	1572 ms	13244 KB	Time limit exceeded
40	Correct	8 ms	13244 KB	Output is correct
41	Incorrect	162 ms	13244 KB	Output isn't correct
42	Correct	13 ms	13244 KB	Output is correct
43	Correct	17 ms	13244 KB	Output is correct
44	Incorrect	27 ms	13244 KB	Output isn't correct
45	Incorrect	239 ms	13244 KB	Output isn't correct
46	Execution timed out	1568 ms	13244 KB	Time limit exceeded
47	Incorrect	31 ms	13244 KB	Output isn't correct
48	Incorrect	30 ms	13244 KB	Output isn't correct
49	Execution timed out	1580 ms	13244 KB	Time limit exceeded
50	Execution timed out	1562 ms	13244 KB	Time limit exceeded

답안 #91382

Compilation message

Subtask #1 66.0 / 100.0

Subtask #1
66.0 / 100.0