結果

問題 No.1640 簡単な色塗り
ユーザー harurunharurun
提出日時 2021-06-16 02:47:15
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,560 bytes
コンパイル時間 867 ms
コンパイル使用メモリ 80,924 KB
実行使用メモリ 32,588 KB
最終ジャッジ日時 2024-06-29 14:34:35
合計ジャッジ時間 5,036 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 4 ms
8,316 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 TLE -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
testcase_44 -- -
testcase_45 -- -
testcase_46 -- -
testcase_47 -- -
testcase_48 -- -
testcase_49 -- -
testcase_50 -- -
testcase_51 -- -
testcase_52 -- -
testcase_53 -- -
07_evil_01.txt -- -
07_evil_02.txt -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:11:1: warning: 'typedef' was ignored in this declaration
   11 | typedef struct edge3{
      | ^~~~~~~
main.cpp: In member function 'void FordFulkerson::add_edge(long long int, long long int, long long int)':
main.cpp:28:48: warning: narrowing conversion of '(((FordFulkerson*)this)->FordFulkerson::G + ((sizetype)(((long unsigned int)to) * 24)))->std::vector<edge3>::size()' from 'std::vector<edge3>::size_type' {aka 'long unsigned int'} to 'long long int' [-Wnarrowing]
   28 |     G[from].push_back((edge3){to,cap,G[to].size()});
      |                                      ~~~~~~~~~~^~
main.cpp:29:50: warning: narrowing conversion of '((((FordFulkerson*)this)->FordFulkerson::G + ((sizetype)(((long unsigned int)from) * 24)))->std::vector<edge3>::size() - 1)' from 'std::vector<edge3>::size_type' {aka 'long unsigned int'} to 'long long int' [-Wnarrowing]
   29 |     G[to].push_back((edge3){from,0,G[from].size()-1});
      |                                    ~~~~~~~~~~~~~~^~
main.cpp: At global scope:
main.cpp:16:1: warning: 'typedef' was ignored in this declaration
   16 | typedef struct FordFulkerson{
      | ^~~~~~~

ソースコード

diff # 

//time測定用
//構築未実装
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <assert.h>
using namespace std;
#define ll long long

typedef struct edge3{
  ll to,cap,rev;
};


typedef struct FordFulkerson{
  const ll INF=1000000000000000000;
  ll MAX_V;
  vector<edge3>* G;
  bool* used;
  FordFulkerson(){}
  FordFulkerson(ll max_v){
    G=new vector<edge3>[max_v];
    used=new bool[max_v];
    MAX_V=max_v;
  }
  void add_edge(ll from,ll to,ll cap){
    G[from].push_back((edge3){to,cap,G[to].size()});
    G[to].push_back((edge3){from,0,G[from].size()-1});
  }
  ll dfs(ll v,ll t,ll f){
    if(v==t)return f;
    used[v]=true;
    for(int i=0;i<G[v].size();i++){
      edge3 &e=G[v][i];
      if(!used[e.to] && e.cap>0){
        ll d=dfs(e.to,t,min(f,e.cap));
        if(d>0){
          e.cap-=d;
          G[e.to][e.rev].cap+=d;
          return d;
        }
      }
    }
    return 0;
  }
  ll max_flow(ll s,ll t){
    ll flow=0;
    for(;;){
      fill(used,used+MAX_V,false);
      ll f=dfs(s,t,INF);
      if(f==0)return flow;
      flow+=f;
    }
    return flow;
  }
};

int main(){
  ll N,A,B;
  cin>>N;
  FordFulkerson F(200002);
  for(int i=0;i<N;i++){
    cin>>A>>B;
    A--;B--;
    F.add_edge(200000,i,1);
    F.add_edge(i,100000+A,1);
    if(A!=B)F.add_edge(i,100000+B,1);
    F.add_edge(100000+i,200001,1);
  }
  //cerr<<"edge added\n";
  ll cnt=F.max_flow(200000,200001);
  //cout<<cnt<<endl;
  if(cnt!=N){
    cout<<"No\n";
    return 0;
  }
  //ここから構築
  cout<<"Yes\n";
  return 0;
}
0