結果

問題 No.19 ステージの選択
ユーザー siman
提出日時 2022-04-08 04:31:45
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 3,742 bytes
コンパイル時間 4,689 ms
コンパイル使用メモリ 146,028 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-28 03:07:33
合計ジャッジ時間 2,490 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cassert>
#include <cfloat>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <limits.h>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string.h>
#include <vector>

using namespace std;
typedef long long ll;

struct Node {
  int i;
  double L;

  Node(int i = -1, double L = -1) {
    this->i = i;
    this->L = L;
  }

  bool operator>(const Node &n) const {
    return L > n.L;
  }
};

typedef vector <vector<int>> Graph;

// 強連結成分分解ライブラリ
class StronglyConnectedComponent {
  public:
    Graph G;
    Graph rG;
    Graph cG;
    vector<int> vs;
    vector<bool> used;
    vector<int> componentId;
    int componentCount;
    int V;

    StronglyConnectedComponent(int V) {
      this->V = V;
      used = vector<bool>(V);
      componentId = vector<int>(V);
      G = Graph(V);
      rG = Graph(V);
    }

    void add_edge(int from, int to) {
      assert(0 <= from < V);
      assert(0 <= to < V);

      G[from].push_back(to);
      rG[to].push_back(from);
    }

    void run() {
      fill(used.begin(), used.end(), false);
      componentCount = 0;
      vs.clear();

      for (int v = 0; v < V; ++v) {
        if (used[v]) continue;

        dfs(v);
      }

      fill(used.begin(), used.end(), false);

      for (int i = vs.size() - 1; i >= 0; --i) {
        int v = vs[i];
        if (used[v]) continue;

        cG.push_back(vector<int>());
        rdfs(v, componentCount++);
      }
    }

  private:
    void dfs(int v) {
      used[v] = true;

      for (int i = 0; i < G[v].size(); ++i) {
        int u = G[v][i];

        if (used[u]) continue;

        dfs(u);
      }

      vs.push_back(v);
    }

    void rdfs(int v, int k) {
      used[v] = true;
      componentId[v] = k;
      cG[k].push_back(v);

      for (int i = 0; i < rG[v].size(); ++i) {
        int u = rG[v][i];

        if (used[u]) continue;

        rdfs(u, k);
      }
    }
};

vector<int> tsort(Graph G, int start, int end) {
  vector<int> ret;

  int degree[end];
  memset(degree, 0, sizeof(degree));

  for (int from = start; from < end; from++) {
    for (int i = 0; i < G[from].size(); i++) {
      int to = G[from][i];
      degree[to]++;
    }
  }

  stack<int> root;

  for (int i = start; i < end; i++) {
    if (degree[i] == 0) {
      root.push(i);
    }
  }

  while (!root.empty()) {
    int from = root.top();
    root.pop();

    ret.push_back(from);

    for (int i = 0; i < G[from].size(); i++) {
      int to = G[from][i];
      degree[to]--;

      if (degree[to] == 0) {
        root.push(to);
      }
    }
  }

  return ret;
}

int main() {
  int N;
  cin >> N;

  StronglyConnectedComponent scc(N);
  vector<int> E[N];
  vector<int> RE[N];
  double L[N];
  int S[N];
  for (int i = 0; i < N; ++i) {
    cin >> L[i] >> S[i];
    S[i]--;
    if (S[i] != i) {
      scc.add_edge(S[i], i);
    }
    E[S[i]].push_back(i);
  }

  scc.run();
  int cnt = scc.componentCount;
  double ans = 0.0;
  bool checked[N];
  memset(checked, false, sizeof(checked));
  Graph G(N);

  for (int i = 0; i < cnt; ++i) {
    vector<int> T = scc.cG[i];
    if (T.size() <= 1) {
      int v = T[0];
      for (int u : E[v]) {
        if (u == v) continue;
        G[v].push_back(u);
      }
      continue;
    }

    double min_l = DBL_MAX;

    for (int v : T) {
      checked[v] = true;
      min_l = min(min_l, L[v] / 2.0);
      ans += L[v] / 2.0;
    }

    ans += min_l;
  }

  vector<int> res = tsort(G, 0, N);
  for (int v : res) {
    if (checked[v]) continue;

    if (checked[S[v]]) {
      ans += L[v] / 2.0;
    } else {
      ans += L[v];
    }

    checked[v] = true;
  }

  cout << fixed << setprecision(1) << ans << endl;

  return 0;
}
0