結果

問題 No.19 ステージの選択
コンテスト
ユーザー SakaTaku
提出日時 2020-10-25 15:42:46
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 1,206 bytes
コンパイル時間 2,013 ms
コンパイル使用メモリ 178,088 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-21 20:51:45
合計ジャッジ時間 2,750 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < n; ++i)
using ll = long long;
using P = pair<int,int>;
int main() {
   cout<<fixed<<setprecision(1);
   int n;cin>>n;
   vector<int> l,s;
   vector<vector<int>> g(n);
   rep(i,n){
      int li,si;cin>>li>>si;
      si--;
      l.push_back(li);
      s.push_back(si);
      g[si].push_back(i);
   }
   double ans=accumulate(l.begin(),l.end(),0)/2.0;
   vector<bool> used(n);
   vector<int> vs;
   function<void (int)> dfs = [&](int v){
      used[v]=true;
      for (auto &&i : g[v])
         if(!used[i])dfs(i);
      vs.push_back(v);
   };
   int Min;
   function<void (int)> rdfs = [&](int v){
      used[v] = true;
      Min=min(Min,l[v]);
      if(!used[s[v]])rdfs(s[v]);
   };
   used=vector<bool>(n,false);
   rep(i,n)if(!used[i])dfs(i);
   used=vector<bool>(n,false);
   vector<bool> used2(n,false);
   function<void (int)> dfs2 = [&](int v){
      used2[v]=true;
      for (auto &&i : g[v])
         if(!used2[i])dfs2(i);
   };
   for (int i = vs.size()-1; i >= 0; i--){
      if(used[vs[i]]||used2[vs[i]])continue;
      Min=100;
      rdfs(vs[i]);
      ans+=Min/2.0;
      dfs2(vs[i]);
   }
   cout<<ans<<endl;
}
0