Submission #91515

#	Time	Username	Problem	Language	Result	Execution time	Memory
91515		mirbek01	Marriage questions (IZhO14_marriage)	C++11	100 / 100	271 ms	4120 KiB

marriage

# include <bits/stdc++.h>

using namespace std;

const int N = 33002;

int n, m, k, mt[N], cnt, used[N], ans, L, R, pt = 1;
vector <int> g[N], gr[N], mr;

bool dfs(int v){
      if(used[v] == cnt)
            return 0;
      used[v] = cnt;
      for(int i = (int)g[v].size() - 1; i >= 0; i --){
            int to = g[v][i];
            if(to < L) break;
            if(mt[to] == -1 || dfs(mt[to])){
                  mt[to] = v;
                  mt[v] = to;
                  return true;
            }
      }
      return false;
}

bool check(){
      while(!mr.empty()){
            int v = mr.back();
            if(mt[v] == -1){
                  cnt ++;
                  if(!dfs(v))
                        return false;
            }
            mr.pop_back();
      }
      return mr.empty();
}

int main(){
      scanf("%d %d %d", &n, &m, &k);

      for(int i = 1; i <= k; i ++){
            int a, b;
            scanf("%d %d", &a, &b);
            gr[a].push_back(b + n);
      }

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

      for(int i = n + 1; i <= n + m; i ++)
            mr.push_back(i);

      for(int j = 0; j < gr[1].size(); j ++){
            int v = gr[1][j];
            g[v].push_back(1);
      }

      for(int i = 1; i <= n; i ++){
            L = i, R = pt;
            while(pt <= n && !check()){
                  pt ++, R = pt;
                  for(int j = 0; j < gr[pt].size(); j ++){
                        int v = gr[pt][j];
                        g[v].push_back(pt);
                  }
            }
            ans += n - pt + 1;
            if(mt[L] != -1){
                  mr.push_back(mt[L]);
                  mt[mt[L]] = -1;
            }
      }

      printf("%d", ans);
}

Compilation message (stderr)

marriage.cpp: In function 'int main()':
marriage.cpp:53:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int j = 0; j < gr[1].size(); j ++){
                      ~~^~~~~~~~~~~~~~
marriage.cpp:62:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                   for(int j = 0; j < gr[pt].size(); j ++){
                                  ~~^~~~~~~~~~~~~~~
marriage.cpp:40: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:44: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: 100 / 100