naoya_t@topcoder

SRM441 Div1 Medium: StrangeCountry

過去問, 練習 | 04:42 |

• 方針は大体合ってた
  • 修正１：島分け間違ってた：２つの島が出会った時に島番号が隅まで伝播してない
  • 追加２：孤立点があった時に-1を返してない
• 以上２点を直してPassed System Test

typedef long long ll;
typedef vector<int> vi;
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())

class StrangeCountry {
 public:
  int transform(vector <string> g) {
    int N=sz(g);
    // 島分け
    vi isle(N); rep(i,N) isle[i]=i;
    rep(i,N-1){
      for(int j=i+1;j<N;j++){
        if(g[i][j]=='Y'){
          // isle[j] = isle[i] = min(isle[j],isle[i]); //←駄目コード
          // ↓修正１===
          int i_=isle[i],j_=isle[j],m_=min(i_,j_);
          rep(k,N) if(isle[k]==i_||isle[k]==j_) isle[k]=m_;
          // ↑修正１===
        }
      }
    }

    // 各島に含まれる町の数を数える
    vi cnt(N,0); rep(i,N) cnt[isle[i]]++;
    // ↓追加２===
    rep(i,N) if(cnt[i]==1) return -1; /// 孤立点があれば -1
    // ↑追加２===

    // 島
    set<int> ic; rep(i,N) if(cnt[i]) ic.insert(i);
    // 島内の道の数
    vi hz(N,0);
    rep(i,N-1){
      for(int j=i+1;j<N;j++){
        if(g[i][j]=='Y') hz[isle[i]]++;
      }
    }

    // 各島内の「余ってる」道の数
    vi ov(N,0); rep(i,N) ov[i]=hz[i]-(cnt[i]-1);
    int s=0,k=0;
    tr(ic,it){
      k++; s+=ov[*it];
    }

    // ぜんぶ繋ぐのに必要なだけの余剰道路があるか
    int nz=k-1;
    if(nz>s) return -1;
    return nz;
  }
};

もうちょっとよく考えれば防げるミスで落ちているのが辛いところ。十分に射程圏内なので焦らず確実に。