Codeforces Round #686 DIV3 E問題 - Number of Simple Paths

Source

Codeforces Round #686 DIV3 E問題
Problem description

問題概要

省略

解法

省略

cLay（version 20201205-1）のコード

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

//no-unlocked
int N, M, A[2d5], B[2d5];
int ps, p[2d5+1];
int incir[2d5], sz[2d5];
graph g;
{
  unionFind uf;
  uf.walloc(2d5);
  REP(rd_int()){
    ll res;
    rd(N,(A--,B--)(N));
    rep(i,N) incir[i] = sz[i] = 0;
    g.setEdge(N,N,A,B);
    ps = g.anUndirectedCycle(p);
    rep(i,ps) incir[p[i]] = 1;
    uf.init(N);
    rep(i,N) if(incir[A[i]] == 0 || incir[B[i]] == 0) uf(A[i], B[i]);
    rep(i,N) sz[uf(i)]++;
    res = (ll) N * (N-1);
    rep(i,N) res -= (ll) sz[i] * (sz[i]-1) / 2;
    wt(res);
  }
}

Current time: 2024年04月17日03時50分04秒
Last modified: 2020年12月05日16時08分23秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF686 CF_DIV3_E
トップページに戻る

Logged in as: unknown user (not login)