Codeforces Round #580 DIV1 D問題/DIV2 F問題 - Almost All

Source

Codeforces Round #580 DIV1 D問題 (2000pt)
Codeforces Round #580 DIV2 F問題 (3000pt)
Problem description

問題概要

省略

解法

省略

cLay（version 20190820-1）のコード

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

//no-unlocked
int N, A[1000], B[1000], C[1000];
wgraph<int> g;

int arr[1001], as;
int r, ok[1001];
int dp[1001], back[1001];

int dfs2(int n, int b){
  int i, j, k, res = 1;

  rep(i,g.es[n]){
    k = g.edge[n][i];
    if(k==b) continue;
    res += dfs2(k, n);
  }

  return res;
}

int cnt;
void dfs(int n, int b, int d, int m, int dm){
  int i, j, k;

  rep(i,g.es[n]){
    if(n==r && ok[i]==dm) continue;
    k = g.edge[n][i];
    if(k==b) continue;
    cnt++;
    g.cost[n][i] = m * (cnt - d);
    dfs(k, n, cnt, m, dm);
  }
}

{
  int i, j, k, p, m;
  rd(N,(A--,B--)(N-1));

  g.setEdge(N,N-1,A,B,C);

  rep(r,N){
    as = 0;
    rep(i,g.es[r]) arr[as++] = dfs2(g.edge[r][i], r);

    rep(i,N+1) dp[i] = 0;
    dp[0] = 1;
    rep(i,as) for(j=N;j>=arr[i];j--) if(!dp[j] && dp[j-arr[i]]){
      dp[j] = 1;
      back[j] = i;
    }

    rep(p,N+1) if(dp[p] && (p+1) * (N-p) - 1 >= 2*N*N/9) break;
    if(p==N+1) continue;
    
    k = p;
    while(k){
      ok[back[k]] = 1;
      k -= arr[back[k]];
    }
    
    cnt = 0;
    dfs(r, -1, 0, 1, 0);
    cnt = 0;
    dfs(r, -1, 0, p+1, 1);
    break;
  }

  rep(i,N) rep(j,g.es[i]){
    k = g.edge[i][j];
    r = g.cost[i][j];
    if(r > 0) wt(i+1, k+1, r);
  }
}

Current time: 2024年04月18日09時25分45秒
Last modified: 2019年08月21日05時10分31秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF580 CF_Div1_D CF_Div2_F
トップページに戻る

Logged in as: unknown user (not login)