結果
問題 |
No.19 ステージの選択
|
ユーザー |
|
提出日時 | 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 |
ソースコード
#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; }