東京工業大学プログラミングコンテスト2019 F問題 - Road Construction

Source

東京工業大学プログラミングコンテスト2019
問題文

問題概要

省略

解法

省略

cLayversion 20190830-1)のコード

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

int N, M, X1, Y1, X2, Y2, C[2d5], S[2d5], T[2d5];

ll dpX1[1d5], dpX2[1d5], dpY1[1d5], dpY2[1d5];
ll dpX[1d5], dpY[1d5];

{
  int i;
  ll res = ll_inf;
  
  rd(N,M,X1--,Y1--,X2--,Y2--,(C,S--,T--)(M));

  rep(i,N) dpX1[i] = dpX2[i] = dpX[i] = ll_inf;
  rep(i,N) dpY1[i] = dpY2[i] = dpY[i] = ll_inf;

  sortA(M,T,S,C);

  dpY1[Y1] = dpY2[Y2] = 0;
  for(i=M-1;i>=0;i--){
    dpY1[S[i]] <?= dpY1[T[i]] + C[i];
    dpY2[S[i]] <?= dpY2[T[i]] + C[i];
  }
  rep(i,N) dpY[i] <?= dpY1[i] + dpY2[i];
  for(i=M-1;i>=0;i--) dpY[S[i]] <?= dpY[T[i]] + C[i];

  sortA(M,S,T,C);
  dpX1[X1] = dpX2[X2] = 0;
  rep(i,M){
    dpX1[T[i]] <?= dpX1[S[i]] + C[i];
    dpX2[T[i]] <?= dpX2[S[i]] + C[i];
  }
  rep(i,N) dpX[i] <?= dpX1[i] + dpX2[i];
  rep(i,M) dpX[T[i]] <?= dpX[S[i]] + C[i];

  res <?= dpX1[Y1] + dpX2[Y2];
  rep(i,N) res <?= dpX[i] + dpY[i];

  wt( if[res==ll_inf, "Impossible", res] );
}

Current time: 2021年09月28日23時13分29秒
Last modified: 2019年09月01日00時50分45秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン: