QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#188712#6561. Fail FastCurious_DroidWA 1ms8012kbC++231.1kb2023-09-26 12:01:032023-09-26 12:01:03

Judging History

你现在查看的是最新测评结果

  • [2023-09-26 12:01:03]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:8012kb
  • [2023-09-26 12:01:03]
  • 提交

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.0l - p[v]), v});
            c[v] = c[v] + p[v] * c[u];
            p[v] = p[u] * p[u];
            pq.insert({c[v] / (1.0l - 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: 7848kb

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: 1ms
memory: 8012kb

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: 5756kb

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