提出 #594025

---

ソースコード 拡げる

#include <bits/stdc++.h>
#define FOR(i, a, b) for(int (i) = (a); (i) <= (b); ++(i))
#define rep(i, n) FOR(i, 0, n - 1)
#define rep1(i, n) FOR(i, 1, n)
#define rrep(i, n) for(int (i) = (n) - 1; (i) >= 0; --(i))
#define all(a) (a).begin(),(a).end()
#define PB push_back
using namespace std;
using ll = long long int;
using vb = vector<bool>;
using vi = vector<int>;
using vd = vector<double>;
using vll = vector<ll>;
using vvb = vector<vb>;
using vvi = vector<vi>;
using vvd = vector<vd>;
using vvll = vector<vll>;
using vvvi = vector<vvi>;
using vvvd = vector<vvd>;
using P = pair<int, int>;
const int INF = 0x7fffffff;
const ll divisor = 1000000007;

const int MAX_V = 150000 * 2;
int V;
vi G[MAX_V];              // グラフの隣接リスト表現 
vi match(MAX_V);          // マッチングのペア
vector<bool> used(MAX_V); // DFSですでに調べたかのグラフ

void add_edge(int u, int v){
  G[u].PB(v);
  G[v].PB(u);
}

// 増加パスをDFSで探す
bool dfs(int v){
  used[v] = true;
  for(int u : G[v]){
    int w = match[u];
    if(w < 0 || !used[w] && dfs(w)){
      match[v] = u;
      match[u] = v;
      return true;
    }
  }
  return false;
}

// 二部グラフの最大マッチングを求める
int bipartite_matching(){
  int res = 0;
  fill(all(match), -1);
  rep(v, V){
    if(match[v] < 0){
      fill(all(used), false);
      if(dfs(v)) res++;
    }
  }
  return res;
}

int main(){
  int N, M;
  cin >> N >> M;
  V = N + M;
  vi A(N);
  vi B(N);
  vi C(M);
  vi D(M);
  rep(i, N) cin >> A[i] >> B[i];
  rep(i, M) cin >> C[i] >> D[i];

  rep(i, N) rep(j, M){
    if(B[i] <= C[j] && D[j] <= A[i]){
      add_edge(i, N + j);
    }
  }
  cout << bipartite_matching() << endl;
  return 0;
}

提出情報

ジャッジ結果