結果

問題 No.1703 Much Matching
ユーザー harurunharurun
提出日時 2021-08-26 21:01:51
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 990 bytes
コンパイル時間 932 ms
コンパイル使用メモリ 87,216 KB
実行使用メモリ 7,156 KB
最終ジャッジ日時 2023-09-30 09:23:47
合計ジャッジ時間 4,882 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 2 ms
4,384 KB
testcase_03 AC 4 ms
4,376 KB
testcase_04 WA -
testcase_05 AC 6 ms
5,148 KB
testcase_06 AC 105 ms
4,620 KB
testcase_07 AC 7 ms
4,376 KB
testcase_08 WA -
testcase_09 WA -
testcase_10 AC 19 ms
4,380 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 AC 3 ms
4,376 KB
testcase_15 WA -
testcase_16 AC 69 ms
4,376 KB
testcase_17 AC 80 ms
4,380 KB
testcase_18 AC 3 ms
4,376 KB
testcase_19 AC 168 ms
4,868 KB
testcase_20 AC 21 ms
4,376 KB
testcase_21 AC 200 ms
5,368 KB
testcase_22 WA -
testcase_23 AC 59 ms
4,508 KB
testcase_24 AC 3 ms
4,376 KB
testcase_25 WA -
testcase_26 WA -
testcase_27 AC 86 ms
4,380 KB
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 AC 385 ms
7,008 KB
testcase_37 AC 10 ms
7,156 KB
権限があれば一括ダウンロードができます

ソースコード

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