結果

問題 No.19 ステージの選択
コンテスト
ユーザー iwata
提出日時 2019-12-03 23:04:16
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 3 ms / 5,000 ms
コード長 2,411 bytes
コンパイル時間 2,868 ms
コンパイル使用メモリ 177,644 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-27 22:45:41
合計ジャッジ時間 2,562 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>

using namespace std;

#define debug(n) cerr << #n << ':' << n << endl;
#define dline    cerr << __LINE__ << endl;

using ll = long long;
template<class T, class U> using P = pair<T,U>;
template<class T> using Heap = priority_queue<T>;
template<class T> using heaP = priority_queue<T,vector<T>,greater<T>>;
template<class T,class U> using umap = unordered_map<T,U>;
template<class T> using uset = unordered_set<T>;

template<class T>
bool ChangeMax(T&a,const T&b){
  if(a >= b) return false;
  a = b;    return true;
}

template<class T>
bool ChangeMin(T&a,const T&b){
  if(a <= b) return false;
  a = b;    return true;  
}

template<class T, size_t N, class U>
void Fill(T (&a)[N], const U&v){
    fill((U*)a,(U*)(a+N),v);
}

template<class T>
istream& operator >> (istream&is, vector<T>&v){
  for(auto&e:v)is >> e;
  return is;
}

struct Scc{
  int vsize,esize;
  vector<vector<int>> ne,re;
  vector<int> od,cs;
  vector<bool> used;
  Scc(vector<vector<int>>g,int vs,int es):
    vsize(vs),esize(es),ne(g),re(vs),cs(vs,-1),used(vs,false)
  {
    for(int i = 0; i < vsize; ++i){
      for(auto&e:ne[i]){
	re[e].push_back(i);
      }
    }
    for(int i = 0; i < vsize; ++i)dfs(i);
    reverse(od.begin(),od.end());
    int y = 0;
    for(int e:od){
      if(cs[e] != -1)continue;
      rdfs(e,y);
      y++;
    }
  }
  int operator[](int idx){
    return cs[idx];
  }
  void dfs(int x){
    if(used[x]) return;
    used[x] = 1;
    for(auto&e:ne[x])dfs(e);
    od.push_back(x);
  }
  void rdfs(int x,int y){
    if(cs[x] != -1)return;
    cs[x] = y;
    for(auto&e:re[x])rdfs(e,y);
  }
};

int main(){
  int n; cin >> n;
  vector<vector<int>> g(n);
  vector<double> level(n);
  for(int i = 0; i < n; ++i){
    int a,b; cin >> a >> b; b--;
    g[b].push_back(i);
    level[i] = a;
  }
  Scc scc(g,n,n);
  set<int> st;
  double sum = 0;
  vector<int> order(n);
  for(int i = 0; i < n; ++i)order[i] = i;
  sort(order.begin(), order.end(), [&](int a, int b){
      if(scc.cs[a] == scc.cs[b]) return level[a] < level[b];
      return scc.cs[a] < scc.cs[b];
    });
  for(int j = 0; j < n; ++j){
    int i = order[j];
    int cs = scc.cs[i];
    if(st.count(cs) == 0){sum += level[i];cerr << i+1 << ':' << 0 << endl;}
    else{ sum += level[i]/2;cerr << i+1 << ':' << 1 << endl;}
    for(int&e:g[i])st.insert(scc.cs[e]);
  }
  cout << fixed << setprecision(1) << sum << endl;
  return 0;
}
0