QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#134532 | #6561. Fail Fast | Noobie_99# | TL | 1ms | 3768kb | C++20 | 1.3kb | 2023-08-03 22:51:40 | 2023-08-03 22:51:41 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define tsolve int t; cin >> t; while(t--) solve
#define debug(x) cerr << __LINE__ << ": "#x" = " << (x) << endl
#define nl '\n'
#define all(x) ::begin(x), ::end(x)
#define sz(x) (int)::size(x)
using ll = long long;
using ld = long double;
struct Thing{
double c, p;
list<int> rec;
};
Thing combine(Thing a, Thing b){
Thing c;
c.c = a.c + a.p*b.c;
c.p = a.p*b.p;
a.rec.splice(a.rec.end(), b.rec);
c.rec = move(a.rec);
return c;
}
bool operator < (Thing a, Thing b){
return a.c / (1.0 - a.p) < b.c / (1.0 - b.p);
}
int n;
vector<Thing> w;
vector<vector<int>> g;
set<Thing> ret;
void dfs(int u){
set<Thing> s;
for(int v : g[u]){
dfs(v);
if(sz(s) < sz(ret)) swap(s, ret);
for(Thing t : ret) s.insert(t);
}
if(u != 0){
Thing me = w[u];
while(!s.empty() && *s.begin() < me){
me = combine(me, *s.begin());
s.erase(s.begin());
}
s.insert(me);
}
swap(s, ret);
}
void solve() {
cin >> n;
w.resize(n+1),g.resize(n+1);
for(int i = 1; i <= n; i++){
double c, p; int d;
cin >> c >> p >> d;
w[i].c = c, w[i].p = p; w[i].rec.push_back(i);
g[d].push_back(i);
}
dfs(0);
for(Thing t : ret){
for(int i : t.rec) cout << i << "\n";
}
}
int main() {
cin.tie(0)->sync_with_stdio(false);
cout << setprecision(16);
solve();
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3724kb
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: 3656kb
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: 0
Accepted
time: 1ms
memory: 3768kb
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:
2 4 3 6 5 7 1 10 8 9
result:
ok correct
Test #4:
score: 0
Accepted
time: 1ms
memory: 3568kb
input:
20 93 0.093030 0 53 0.056639 0 39 0.021549 0 48 0.069268 3 58 0.009572 4 22 0.015083 1 27 0.024351 5 68 0.085055 7 48 0.031563 5 46 0.025067 9 15 0.095445 2 57 0.011233 6 97 0.028239 2 8 0.060758 6 59 0.097330 13 34 0.052120 3 73 0.055127 11 53 0.004135 12 24 0.051183 5 56 0.027001 13
output:
3 16 4 2 11 5 19 7 9 10 8 17 1 6 14 12 18 13 20 15
result:
ok correct
Test #5:
score: 0
Accepted
time: 1ms
memory: 3660kb
input:
20 971329 0.076234 0 996879 0.012978 0 994191 0.056803 0 978400 0.080792 1 907508 0.008858 4 992071 0.057419 2 901661 0.089621 6 912521 0.051943 5 979169 0.040201 5 904759 0.083405 7 928478 0.092658 7 980034 0.054747 3 906344 0.053231 10 907474 0.090196 8 927695 0.023153 4 995464 0.009387 2 984650 0...
output:
2 16 6 7 10 13 17 19 20 11 1 4 5 15 8 14 18 9 3 12
result:
ok correct
Test #6:
score: 0
Accepted
time: 1ms
memory: 3604kb
input:
20 54 0.952741 0 41 0.912397 0 11 0.963309 0 66 0.915806 3 47 0.919191 4 51 0.906473 5 24 0.989650 6 97 0.964070 7 56 0.997215 1 39 0.981950 2 50 0.994037 2 92 0.942000 7 97 0.900405 3 53 0.950071 6 16 0.980631 14 63 0.950876 10 49 0.995183 15 20 0.908520 5 71 0.949757 16 76 0.972330 9
output:
3 2 4 5 18 6 13 14 15 1 10 16 19 7 12 8 9 20 11 17
result:
ok correct
Test #7:
score: 0
Accepted
time: 1ms
memory: 3744kb
input:
20 933154 0.904059 0 929160 0.911627 0 999437 0.921760 0 991335 0.904136 1 903530 0.943148 4 904464 0.921035 2 944382 0.912394 6 990971 0.982189 7 941308 0.959290 4 993916 0.945081 7 924496 0.989350 1 938782 0.958578 4 964442 0.997198 11 964358 0.938647 10 911972 0.943888 5 975140 0.993873 4 995611 ...
output:
1 4 2 6 7 3 5 15 10 14 20 12 19 9 11 13 17 8 18 16
result:
ok correct
Test #8:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
1 10 0.5 0
output:
1
result:
ok correct
Test #9:
score: 0
Accepted
time: 1ms
memory: 3628kb
input:
2 100 0.8 0 200 0.7 0
output:
1 2
result:
ok correct
Test #10:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
2 10 0.5 0 5 0.4 1
output:
1 2
result:
ok correct
Test #11:
score: 0
Accepted
time: 1ms
memory: 3596kb
input:
2 1000 0.7 2 1 0.6 0
output:
2 1
result:
ok correct
Test #12:
score: -100
Time Limit Exceeded
input:
100000 938188 0.740681 0 575610 0.965656 1 937341 0.842524 2 817797 0.945396 3 602563 0.818956 4 893939 0.900203 5 952148 0.810399 6 538333 0.960769 7 550079 0.908188 8 676338 0.795726 9 546675 0.529045 10 542108 0.581119 11 963201 0.665127 12 564484 0.897025 13 504952 0.844118 14 673675 0.777947 15...