제출 #90400

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
90400		mirbek01	Marriage questions (IZhO14_marriage)	C++17	66 / 100	1586 ms	5244 KiB

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(){
      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);
      }

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

      int pt = 1;

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

      printf("%d", ans);
}

컴파일 시 표준 에러 (stderr) 메시지

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