結果

問題 No.19 ステージの選択
ユーザー iwata
提出日時 2019-12-03 22:29:18
言語 C++11
(gcc 4.8.5)
結果
WA   .
実行時間 -
コード長 2,087 Byte
コンパイル時間 1,603 ms
使用メモリ 1,640 KB
最終ジャッジ日時 2019-12-03 22:29:21

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
01.txt WA -
02.txt AC 4 ms
1,604 KB
03.txt WA -
04.txt WA -
05.txt WA -
06.txt WA -
07.txt WA -
08.txt WA -
09.txt WA -
10.txt WA -
99_system_test1.txt WA -
system_test1.txt AC 4 ms
1,608 KB
system_test2.txt AC 3 ms
1,604 KB
system_test3.txt AC 3 ms
1,604 KB
system_test4.txt WA -
system_test5.txt WA -
system_test6.txt WA -
system_test7.txt WA -
system_test8.txt WA -
system_test9.txt WA -
system_test10.txt WA -
system_test11.txt WA -
system_test12.txt WA -
system_test13.txt WA -
テストケース一括ダウンロード

ソースコード

diff #
#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[i].push_back(b);
    level[i] = a;
  }
  Scc scc(g,n,n);
  set<int> st;
  double sum = 0;
  for(int i = 0; i < n; ++i){
    int cs = scc.cs[i];
    if(st.count(cs) == 0)sum += level[i];
    else sum += level[i]/2;
    st.insert(scc.cs[g[i][0]]);
  }
  cout << fixed << setprecision(1) << sum << endl;
  return 0;
}
0