保存されている過去のバージョンの一覧

2020年09月13日14時08分07秒

Codeforces Round #670 DIV2 C問題 - Link Cut Centroids

Source

Codeforces Round #670 DIV2 C問題 (1500pt)
Problem description

問題概要

省略

解法

省略

cLay（version 20200913-1）のコード

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

//no-unlocked
int N, A[1d5], B[1d5];
graph g;
int sz[1d5], cn[1d5], dep[1d5], dis[1d5];
{
  REP(rd_int()){
    int mn, mnc, x, y, i, j, k;
    rd(N,(A--,B--)(N-1));
    g.setEdge(N,N-1,A,B);
    g.SubTreeSize(0, sz);
    g.getDist(0, dep);
    rep(i,N) cn[i] = N - sz[i];
    rep(i,N) rep[g.edge[i]](j,g.es[i]) if(dep[j] > dep[i]) cn[i] >?= sz[j];

    mn = min(cn(N));
    mnc = arrCountVal(N, cn, mn);
    if(mnc==1){
      rep(2) wt(A[0]+1, B[0]+1);
      continue;
    }

    x = y = -1;
    rep(i,N) if(cn[i]==mn){
      if(x==-1) x = i, continue;
      if(y==-1) y = i, continue;
    }
    rep(i,N) if(g.es[i]==1) break;
    k = g.edge[i][0];
    g.getDist(i,dis);
    j = if[dis[x] > dis[y], x, y];
    wt(i+1, k+1);
    wt(i+1, j+1);
  }
}

Current time: 2024年04月26日00時34分02秒
Last modified: 2020年09月13日14時08分07秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF670 CF_Div2_C
トップページに戻る

Logged in as: unknown user (not login)

ログイン：