結果

問題 No.19 ステージの選択
ユーザー kenkooookenkoooo
提出日時 2016-06-12 22:36:17
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 4,050 bytes
コンパイル時間 1,906 ms
コンパイル使用メモリ 174,596 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-23 10:05:17
合計ジャッジ時間 2,858 ms
ジャッジサーバーID
(参考情報)
judge5 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

/*
_ooOoo_
o8888888o
88" . "88
(| -_- |)
O\ = /O
____/`---'\____
.' \\| |// `.
/ \\||| : |||// \
/ _||||| -:- |||||- \
| | \\\ - /// | |
| \_| ''\---/'' | |
\ .-\__ `-` ___/-. /
___`. .' /--.--\ `. . __
."" '< `.___\_<|>_/___.' >'"".
| | : `- \`.;`\ _ /`;.`/ - ` : | |
\ \ `-. \_ __\ /__ _/ .-` / /
======`-.____`-.___\_____/___.-`____.-'======
`=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
pass System Test!
*/
#include <bits/stdc++.h>
using namespace std;
template <typename T>
std::ostream &operator<<(std::ostream &out, const std::vector<T> &v) {
if (!v.empty()) {
out << '[';
std::copy(v.begin(), v.end(), std::ostream_iterator<T>(out, ", "));
out << "\b\b]";
}
return out;
}
template <typename T1, typename T2>
std::ostream &operator<<(std::ostream &out, const std::pair<T1, T2> &p) {
out << "[" << p.first << ", " << p.second << "]";
return out;
}
template <class T, class U>
void chmin(T &t, U f) {
if (t > f) t = f;
}
template <class T, class U>
void chmax(T &t, U f) {
if (t < f) t = f;
}
template <typename T>
void uniq(vector<T> &v) {
v.erase(unique(v.begin(), v.end()), v.end());
}
class StronglyConnectedComponents {
private:
StronglyConnectedComponents() {}
int N;
std::vector<int> cmp;
std::vector<std::vector<int>> super_graph;
size_t componentsSize;
void dfs(int v, std::vector<bool> &used, std::vector<int> &vs,
const std::vector<std::vector<int>> &g) {
used[v] = true;
for (int w : g[v])
if (!used[w]) dfs(w, used, vs, g);
vs.push_back(v);
}
void rdfs(int v, int k, std::vector<bool> &used,
const std::vector<std::vector<int>> &rg) {
used[v] = true;
cmp[v] = k;
for (int w : rg[v])
if (!used[w]) rdfs(w, k, used, rg);
}
public:
StronglyConnectedComponents(const std::vector<std::vector<int>> &g) {
N = g.size();
cmp.resize(N);
std::vector<std::vector<int>> rg(N);
for (int i = 0; i < N; ++i)
for (int v : g[i]) rg[v].push_back(i);
std::vector<bool> used(N, false);
std::vector<int> vs;
for (int i = 0; i < N; ++i)
if (!used[i]) dfs(i, used, vs, g);
used.assign(N, false);
componentsSize = 0;
for (int i = vs.size() - 1; i >= 0; i--)
if (!used[vs[i]]) rdfs(vs[i], componentsSize++, used, rg);
super_graph.resize(componentsSize);
for (int i = 0; i < N; ++i) {
std::vector<bool> vis(componentsSize, false);
for (int v : g[i]) {
if (vis[cmp[v]] || cmp[v] == cmp[i]) continue;
super_graph[cmp[i]].push_back(cmp[v]);
vis[cmp[v]] = true;
}
}
}
std::vector<int> getComponentIDs() { return cmp; }
std::vector<std::vector<int>> getComponentList() {
std::vector<std::vector<int>> clist(componentsSize);
for (int i = 0; i < N; ++i) clist[cmp[i]].push_back(i);
return clist;
}
std::vector<std::vector<int>> getSuperGraph() { return super_graph; }
int size() { return componentsSize; }
};
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int N;
cin >> N;
vector<vector<int>> g(N);
vector<int> level(N);
for (int i = 0; i < N; ++i) {
int S;
cin >> level[i] >> S;
S--;
g[S].push_back(i);
}
StronglyConnectedComponents scc(g);
vector<vector<int>> sg = scc.getSuperGraph();
vector<vector<int>> rsg(sg.size());
for (int i = 0; i < sg.size(); ++i)
for (int v : sg[i]) {
rsg[v].push_back(i);
}
vector<vector<int>> clist = scc.getComponentList();
double ans = 0.0;
for (int i = 0; i < clist.size(); ++i) {
int sum = 0;
int mi = 1e9;
for (int c : clist[i]) {
sum += level[c];
mi = min(mi, level[c]);
}
if (rsg[i].size() == 0) {
sum -= mi;
ans += mi;
}
ans += (sum / 2.0);
}
printf("%.1f\n", ans);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0