結果

問題 No.1703 Much Matching
ユーザー harurun
提出日時 2021-08-26 21:01:51
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 990 bytes
コンパイル時間 1,115 ms
コンパイル使用メモリ 84,864 KB
最終ジャッジ日時 2025-01-24 02:06:34
ジャッジサーバーID
（参考情報） 		judge4 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17 WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <atcoder/dsu>
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
using namespace atcoder;

int lcs(vector<int>& S, vector<int>& T){
  vector<vector<int>> dp(S.size()+1,vector<int>(T.size()+1,0));
  for(int i=1;i<S.size()+1;i++){
    for(int j=1;j<T.size()+1;j++){
      if(S.at(i-1)==T.at(j-1)){
        dp.at(i).at(j)=dp.at(i-1).at(j-1)+1;
      }else{
        dp.at(i).at(j)=max(dp.at(i-1).at(j),dp.at(i).at(j-1));
      }
    }
  }
  return dp.at(S.size()).at(T.size());
}

int main(){
  int N,M,Q,a,b;
  cin>>N>>M>>Q;
  dsu uf(N+M);
  for(int i=0;i<Q;i++){
    cin>>a>>b;
    uf.merge(a-1,N+b-1);
  }
  vector<int>A(N),B(M);
  for(int i=0;i<N;i++){
    A.at(i)=i;
  }
  for(int i=0;i<M;i++){
    B.at(i)=N+i;
  }
  vector<vector<int>>g=uf.groups();
  for(vector<int>i:g){
    for(int j:i){
      if(j<N){
        A.at(j)=i.at(0);
      }else{
        B.at(j-N)=i.at(0);
      }
    }
  }
  printf("%d\n",lcs(A,B));
  return 0;
}
0