結果

問題 No.19 ステージの選択
ユーザー pessimist
提出日時 2024-10-22 15:26:29
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 4 ms / 5,000 ms
コード長 2,751 bytes
コンパイル時間 2,388 ms
コンパイル使用メモリ 213,348 KB
最終ジャッジ日時 2025-02-24 22:17:08
ジャッジサーバーID
（参考情報） 		judge3 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
struct SCC{
  int V = 0;
  vector<vector<int>> adj;
  vector<int> tour_index, low_link;
  int tour;
 
  vector<int> stack;
  vector<bool> in_stack;
 
  vector<vector<int>> components;
  vector<int> which_component;
 
  SCC(int v = 0) : V(v), adj(V, vector<int>()){}
  SCC(const vector<vector<int>>& adj_) : V(static_cast<int>(size(adj))), adj(adj) {}
  
  void add_edge(int a, int b){
    adj[a].emplace_back(b);
  }
 
  //Tarjan's Algorithm
  void dfs(int node){
    tour_index[node] = low_link[node] = tour++;
    stack.push_back(node);
    in_stack[node] = true;
 
    for(const int& neighbour: adj[node]){
      if(tour_index[neighbour] < 0){
        //neighbour is the part of subtree
        dfs(neighbour);
        low_link[node] = min(low_link[node], low_link[neighbour]);
      }
      else if(in_stack[neighbour]){
        // neighbour is our tree ancestor, so it's a candidate for minimizing low_link time for node
        low_link[node] = min(low_link[node], tour_index[neighbour]);
      }
    }
 
    if(low_link[node] == tour_index[node]){
      // node is the highest node in a SCC, which includes everything on the stack up to it.
      components.emplace_back();
      vector<int> &component = components.back();
 
      int x;
      do{
        assert(!stack.empty());
        x = stack.back();
        stack.pop_back();
        in_stack[x] = false;
        component.emplace_back(x);
        which_component[x] = size(components) - 1;
      }while(x != node);
    }
  }
 
  void build(){
    tour_index.assign(V, -1);
    low_link.assign(V, -1);
    which_component.assign(V, -1);
 
    stack.clear();
    stack.reserve(V);
    in_stack.assign(V, false);
    tour = 0;
 
    //Note that Tarjan's Algorithm provides the SCCs in reverse topological order
    components = {};
    for(int i=0; i<V; ++i)
      if(tour_index[i] < 0)
        dfs(i);
  }
};

int main(){
  cin.tie(nullptr)->sync_with_stdio(false);
  int N; cin >> N;
  vector<int> l(N), s(N); // (diff, stage that must be cleared before to halve the diff)

  SCC scc(N);
  for(int i = 0; i < N; ++i){
    cin >> l[i] >> s[i];
    --s[i];
    scc.add_edge(s[i], i);
    l[i] *= 2;
  }
  scc.build();

  int ans = 0;
  auto comp = scc.components;
  for(auto& c: comp){
    vector<int> t;
    for(auto& v: c){
      t.emplace_back(l[v]);
    }
    if(t.size() == 1){
      if(s[c[0]] == c[0]){
        ans += t[0];
      } else{
        ans += t[0] / 2;
      }
    } else{
      sort(t.begin(), t.end());
      for(int j = 0; j < t.size(); ++j){
        if(j == 0) ans += t[j];
        else ans += t[j] / 2;
      }
    }
  }
  cout << (ans >> 1);
  if(ans & 1) cout << ".5";
  else cout << ".0";
  cout << endl;
  return 0;
}
0