Codeforces Round #680 (based on Moscow Team Olympiad) DIV1 C問題/DIV2 E問題 - Team-Building

Source

Codeforces Round #680 (based on Moscow Team Olympiad) DIV1 C問題 (1500pt)
Codeforces Round #680 (based on Moscow Team Olympiad) DIV2 E問題 (2500pt)
Problem description

問題概要

省略

解法

省略

cLay（version 20201102-1）のコード

C++に変換後のコードはこちら

//no-unlocked
int N, M, K, C[5d5], A[5d5], B[5d5];
int ng[5d5];
map<pair<int,int>,int> c2;
vector<int> ind[5d5];
{
  int x, y, z = 0;
  pair<int,int> p;
  ll res, ok = 0;
  rollbackUnionFind uf;
  rd(N,M,K,(C--)(N),(A--,B--)(M));
  uf.walloc(2N, 1);

  rep(i,M){
    (x, y) = (A[i], B[i]);
    if(C[x] == C[y]) uf(x,y+N), uf(x+N,y), continue;
    p = make_pair(min(C[x], C[y]), max(C[x], C[y]));
    if(c2.count(p)==0) c2[p] = z++;
    ind[c2[p]].push_back(i);
  }

  rep(i,N) if(uf(i)==uf(i+N)) ng[C[i]] = 1;
  rep(i,K) if(!ng[i]) ok++;
  res = ok * (ok-1) / 2;

  uf.snapshot();
  rep(k,z){
    if(ng[C[A[ind[k][0]]]] || ng[C[B[ind[k][0]]]]) continue;
    uf.rollback();
    for(int i : ind[k]) uf(A[i], B[i]+N),  uf(A[i]+N, B[i]);
    for(int i : ind[k]) if(uf(A[i]) == uf(A[i]+N) || uf(B[i]) == uf(B[i]+N)) res--, break_continue;
  }

  wt(res);
}

Current time: 2024年04月26日02時42分49秒
Last modified: 2020年11月03日08時14分43秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF680 CF_DIV1_C CF_DIV2_E
トップページに戻る

Logged in as: unknown user (not login)