QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#188709#6561. Fail FastCurious_DroidWA 1ms3644kbC++231.1kb2023-09-26 11:58:542023-09-26 11:58:55

Judging History

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

  • [2023-09-26 11:58:55]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3644kb
  • [2023-09-26 11:58:54]
  • 提交

answer

#include <iostream>
#include <set>

int label[100005], head[100005], tail[100005], nxt[100005];
int getparent(int x)
{
    return (label[x] == x) ? x : label[x] = getparent(label[x]);
}

int main()
{
    int n;
    std::cin >> n;
    int d[n + 1];
    long double c[n + 1], p[n + 1];

    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";
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3644kb

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

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: 0ms
memory: 3620kb

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