QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#188711 | #6561. Fail Fast | Curious_Droid | WA | 1ms | 7856kb | C++23 | 1.1kb | 2023-09-26 11:59:44 | 2023-09-26 11:59:44 |
Judging History
answer
#include <iostream>
#include <set>
int n, d[100005], label[100005], head[100005], tail[100005], nxt[100005];
long double c[100005], p[100005];
int getparent(int x)
{
return (label[x] == x) ? x : label[x] = getparent(label[x]);
}
int main()
{
std::cin >> n;
std::set<std::pair<long double, int>> pq;
for (int i = 1; i <= n; i++)
{
std::cin >> c[i];
std::cin >> p[i];
std::cin >> d[i];
label[i] = head[i] = tail[i] = i;
pq.insert({c[i] / (1 - p[i]), i});
}
while (!pq.empty())
{
int u = (*pq.begin()).second;
pq.erase(pq.begin());
int v = getparent(d[u]);
label[u] = v;
nxt[tail[v]] = head[u];
tail[v] = tail[u];
if (v != 0)
{
pq.erase({c[v] / (1 - p[v]), v});
c[v] = c[v] + p[v] * c[u];
p[v] = p[u] * p[u];
pq.insert({c[v] / (1 - p[v]), v});
}
}
for (int i = nxt[0]; i != 0; i = nxt[i])
{
std::cout << i << "\n";
}
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 7852kb
input:
4 100 0.5 0 200 0.1 1 10 0.5 2 10 0.9 0
output:
4 1 2 3
result:
ok correct
Test #2:
score: 0
Accepted
time: 0ms
memory: 7856kb
input:
4 84 0.716 0 91 0.115 0 19 0.640 1 103 0.455 0
output:
2 1 3 4
result:
ok correct
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 5808kb
input:
10 18 0.574073 0 13 0.540309 0 13 0.539018 2 12 0.572910 2 15 0.570616 4 16 0.510215 3 17 0.504083 5 19 0.539297 1 19 0.577271 7 10 0.578346 1
output:
1 10 2 4 3 6 5 7 8 9
result:
wrong answer your plan is not optimal