QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#227761#6561. Fail FastNerovix#WA 1ms7428kbC++20969b2023-10-27 22:45:202023-10-27 22:45:20

Judging History

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

  • [2023-10-27 22:45:20]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:7428kb
  • [2023-10-27 22:45:20]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 5;

int n;

int t[MAXN], fa[MAXN];
ll sum[MAXN];
double p[MAXN];
vector<int> G[MAXN];

priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> q;

inline void dfs(int x) {
    sum[x] = t[x];
    for (auto y : G[x]) 
        dfs(y), sum[x] += sum[y];        
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);   
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> t[i] >> p[i] >> fa[i];
        if(fa[i]) G[fa[i]].push_back(i);
    }
    
    for(int i = 1; i <= n; i++) if(!fa[i]) 
        dfs(i), q.push(make_pair(p[i] * sum[i], i));    
    while(!q.empty()) {
        int x = q.top().second; q.pop();
        cout << x << '\n';
        for(auto y : G[x]) q.push(make_pair(p[y] * sum[y], y));
    }
    return 0;
}
/*
4
100 0.5 0
200 0.1 1
10 0.5 2
10 0.9 0
*/

详细

Test #1:

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

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: -100
Wrong Answer
time: 1ms
memory: 7120kb

input:

4
84 0.716 0
91 0.115 0
19 0.640 1
103 0.455 0

output:

2
4
1
3

result:

wrong answer your plan is not optimal