結果

問題 No.19 ステージの選択
ユーザー reirei
提出日時 2024-02-24 04:02:26
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 3 ms / 5,000 ms
コード長 2,999 bytes
コンパイル時間 1,515 ms
コンパイル使用メモリ 132,960 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-09-29 09:48:08
合計ジャッジ時間 2,520 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 2 ms
6,816 KB
testcase_04 AC 2 ms
6,820 KB
testcase_05 AC 2 ms
6,816 KB
testcase_06 AC 2 ms
6,824 KB
testcase_07 AC 2 ms
6,820 KB
testcase_08 AC 2 ms
6,816 KB
testcase_09 AC 2 ms
6,816 KB
testcase_10 AC 2 ms
6,820 KB
testcase_11 AC 2 ms
6,816 KB
testcase_12 AC 3 ms
6,820 KB
testcase_13 AC 3 ms
6,820 KB
testcase_14 AC 2 ms
6,816 KB
testcase_15 AC 3 ms
6,816 KB
testcase_16 AC 2 ms
6,816 KB
testcase_17 AC 2 ms
6,816 KB
testcase_18 AC 3 ms
6,820 KB
testcase_19 AC 2 ms
6,816 KB
testcase_20 AC 2 ms
6,816 KB
testcase_21 AC 2 ms
6,820 KB
testcase_22 AC 2 ms
6,820 KB
testcase_23 AC 2 ms
6,820 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <cmath>
#include <cstdint>
#include <iostream>
#include <iterator>
#include <map>
#include <regex>
#include <set>
#include <string>
#include <vector>

using namespace std;
using i8 = int8_t;
using i32 = int;
using i64 = long long;
using i128 = __int128;
using u64 = unsigned long long;
using ll = long long;

#define rep(i, n) for (i64 i = 0; i < (i64)n; i++)
#define rep_r(i, a, b) for (i64 i = a; i < (i64)n; i++)

void _main();
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  _main();
}

i64 pow(i64 x, i64 n) {
  long long ret = 1;
  while (n > 0) {
    if (n & 1)
      ret *= x; // n の最下位bitが 1 ならば x^(2^i) をかける
    x *= x;
    n >>= 1; // n を1bit 左にずらす
  }
  return ret;
}

template <typename T> string to_string(vector<T> v) {
  string res = "[";
  for (i64 i = 0; i < size(v); i++) {
    res += to_string(v[i]);
    if (i < size(v) - 1) {
      res += ", ";
    }
  }
  res += "]";
  return res;
}

template <typename T>
vector<vector<T>> rotate(vector<vector<T>> &vec, i64 H, i64 W) {
  vector<vector<T>> res(W, vector<T>(H));
  for (i64 i = 0; i < W; i++) {
    for (i64 j = 0; j < H; j++) {
      res[i][j] = vec[j][W - 1 - i];
    }
  }
  return res;
}
vector<pair<u64, u64>> grid_4d = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
vector<pair<u64, u64>> grid_8d = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1},
                                  {0, 1},   {1, -1}, {1, 0},  {1, 1}};

string out_base(i64 n, i64 len, i64 base) {
  string s;
  for (i64 i = 0; i < len; i++) {
    s += to_string(n % base) + " ";
    n /= base;
  }
  return s;
}
const i64 inf = 1ll << 60;

i64 n, cnt = 0;
i64 l[150];
i64 s[150];
vector<i64> g[20000];
i64 ord[20000];
i64 low[20000];
vector<i64> visited;
vector<vector<i64>> scc;

void dfs(i64 i) {
  if (ord[i] == inf) {
    return;
  }
  ord[i] = cnt;
  low[i] = cnt;
  cnt++;
  visited.push_back(i);
  for (i64 ni : g[i]) {
    if (ord[ni] == n) {
      dfs(ni);
      low[i] = min(low[i], low[ni]);
    } else {
      low[i] = min(low[i], ord[ni]);
    }
  }
  if (ord[i] == low[i]) {
    vector<i64> e;
    while (1) {
      i64 ni = visited.back();
      visited.pop_back();
      ord[ni] = inf;
      e.push_back(ni);
      if (i == ni) {
        break;
      }
    }
    scc.push_back(e);
  }
}

void _main() {
  cin >> n;
  i64 sum = 0;
  for (i64 i = 0; i < n; i++) {
    cin >> l[i] >> s[i];
    s[i]--;
    g[s[i]].push_back(i);
    sum += l[i];
  }
  for (i64 i = 0; i < n; i++) {
    ord[i] = n;
    low[i] = n;
  }
  for (i64 i = 0; i < n; i++) {
    dfs(i);
  }
  reverse(scc.begin(), scc.end());
  vector<bool> ok(n, false);
  for (auto v : scc) {
    bool any = false;
    for (auto v : v) {
      if (ok[s[v]]) {
        any = true;
      }
    }
    if (!any) {
      i64 m = inf;
      for (auto v : v) {
        m = min(m, l[v]);
      }
      sum += m;
    }
    for (auto v : v) {
      ok[v] = true;
    }
  }
  cout << sum / 2 << (sum % 2 == 0 ? ".0" : ".5") << "\n";
}
0