Codeforces Round #580 DIV1 D問題 (2000pt)
Codeforces Round #580 DIV2 F問題 (3000pt)
Problem description
省略
省略
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年05月08日13時10分50秒
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)