QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#189205 | #6561. Fail Fast | ucup-team870 | RE | 164ms | 13956kb | C++14 | 1.5kb | 2023-09-27 00:30:45 | 2023-09-27 00:30:46 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=l; i<=r; i++)
#define IOS {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);}
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int N = 100010;
int d[N], fa[N], ans[N], cnt, tail[N], nxt[N], vis[N];
long double c[N], p[N];
int find(int x) {
return x == fa[x]? x: fa[x] = find(fa[x]);
}
struct cmp {
bool operator() (int a, int b) {
return c[a] * (1-p[b]) < c[b] * (1-p[a]);
}
};
multiset<int, cmp> s;
int main() {
int n; scanf("%d", &n);
rep (i, 1, n) {
scanf("%Lf%Lf%d", &c[i], &p[i], &d[i]);
fa[i] = i;
}
rep (i, 1, n) {
s.insert(i);
tail[i] = i;
}
vis[0] = 1;
rep (i, 1, n) {
int t = *s.begin();
s.erase(s.begin());
t = find(t);
if (!vis[d[t]]) {
int f = find(d[t]);
s.erase(s.find(f));
fa[t] = f;
long double cc = c[f] + p[f] * c[t], pp = p[f] * p[t];
c[f] = cc, p[f] = pp;
nxt[tail[f]] = t;
tail[f] = tail[t];
s.insert(f);
}
else {
do {
ans[++cnt] = t;
vis[t] = 1;
t = nxt[t];
} while (t);
}
}
assert(n<=cnt);
rep (i, 1, cnt) cout << ans[i] <<'\n';
return 0;
}
/*
4
100 0.5 0
200 0.1 1
10 0.5 2
10 0.9 0*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5764kb
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: 3724kb
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: 3656kb
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: 0ms
memory: 3728kb
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: 0ms
memory: 3728kb
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: 3552kb
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: 0ms
memory: 3652kb
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: 3640kb
input:
1 10 0.5 0
output:
1
result:
ok correct
Test #9:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
2 100 0.8 0 200 0.7 0
output:
1 2
result:
ok correct
Test #10:
score: 0
Accepted
time: 1ms
memory: 3724kb
input:
2 10 0.5 0 5 0.4 1
output:
1 2
result:
ok correct
Test #11:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
2 1000 0.7 2 1 0.6 0
output:
2 1
result:
ok correct
Test #12:
score: 0
Accepted
time: 164ms
memory: 13672kb
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...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok correct
Test #13:
score: 0
Accepted
time: 35ms
memory: 13844kb
input:
100000 501234 0.500516 0 501214 0.503354 1 501013 0.504058 2 502546 0.502962 3 500273 0.505433 4 500197 0.505874 5 505941 0.500204 6 500455 0.506393 7 506433 0.500626 8 503652 0.503861 9 500935 0.507151 10 501370 0.506725 11 502595 0.506236 12 503444 0.505698 13 501723 0.508031 14 505738 0.504150 15...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok correct
Test #14:
score: 0
Accepted
time: 82ms
memory: 13668kb
input:
100000 768956 0.999996 0 686063 0.999982 1 817790 0.999964 2 897069 0.999958 3 940413 0.999956 4 879098 0.999957 5 687880 0.999964 6 663602 0.999959 7 816976 0.999944 8 572136 0.999958 9 653227 0.999946 10 972448 0.999914 11 836815 0.999920 12 617305 0.999941 13 934633 0.999903 14 757071 0.999917 15...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok correct
Test #15:
score: 0
Accepted
time: 129ms
memory: 13848kb
input:
100000 686602 0.755750 0 606835 0.951986 0 713656 0.504635 0 609527 0.663061 0 752558 0.613758 0 997011 0.880758 0 905135 0.574450 0 732880 0.774286 0 573515 0.609711 0 899010 0.630653 0 664787 0.949029 0 649162 0.965284 0 582075 0.957310 0 939848 0.848816 0 743139 0.738017 0 577134 0.723893 0 91476...
output:
253 67 161 137 179 1001 287 255 3403 97013 304 33 428 135 212 344 237 110 234 35 149 2447 65686 7360 281 267 357 235 11969 10350 55117 23101 44394 90 345 32287 94695 21214 188 5602 3 12430 219 17907 55 71206 152 87789 70 305 9 90656 238 210 5552 72776 205 236 6216 1136 648 1276 7802 92691 249 2763 5...
result:
ok correct
Test #16:
score: 0
Accepted
time: 145ms
memory: 13848kb
input:
100000 866461 0.563475 0 566909 0.892585 1 794999 0.608805 1 572103 0.501998 1 889513 0.669248 4 712553 0.620050 3 721255 0.898776 3 731219 0.870250 5 958886 0.933100 5 946557 0.758386 1 829823 0.901169 6 513249 0.679404 6 707379 0.965023 2 686267 0.691424 13 790432 0.772695 3 630098 0.867609 11 975...
output:
1 4 255 1463 17335 2114 14926 25657 17157 19416 25749 33301 67686 2 43930 34070 382 70 4349 739 5234 2679 10128 14274 10413 35 1243 11751 30407 49724 94468 92693 98817 28424 41338 79762 220 4584 702 10034 40074 1056 32441 2754 5745 5840 61325 61426 28243 3 6 12 9550 123 1113 15255 26543 1657 3838 31...
result:
ok correct
Test #17:
score: 0
Accepted
time: 131ms
memory: 13956kb
input:
100000 724633 0.992242 0 519908 0.739362 1 841119 0.933434 2 791058 0.900611 3 675619 0.998138 4 764793 0.750214 5 749590 0.659667 6 999818 0.893057 7 643755 0.894506 8 843096 0.848621 9 948647 0.664404 10 914991 0.753675 11 923272 0.619427 12 937334 0.894654 13 811519 0.627730 14 610149 0.981146 15...
output:
1 2 3534 1245 9813 18840 3255 17466 2329 5499 10237 28651 58928 63019 72223 3738 79615 1525 59464 8134 8727 390 71564 7842 10595 99232 89273 10764 35414 14731 20737 89154 14055 3552 69171 11710 17881 33462 11875 19460 22920 24318 14524 45990 7751 9761 8722 75995 3968 9240 65365 40991 80419 12494 262...
result:
ok correct
Test #18:
score: 0
Accepted
time: 150ms
memory: 13784kb
input:
100000 526633 0.902698 0 515821 0.957942 1 871718 0.810818 2 920847 0.633590 3 826181 0.806362 4 876673 0.742829 5 614618 0.612000 6 853505 0.831590 7 511485 0.830238 8 632217 0.794467 9 671254 0.883474 10 695783 0.701932 11 862825 0.611140 12 678224 0.856628 13 659493 0.947587 14 893183 0.970325 15...
output:
1 2 52258 3 4 5 6 7 8 9 10 63310 11 12 13 55535 70001 14 94065 87644 15 16 17 18 19 20 21 22 23 61227 24 25 26 27 54174 28 29 30 31 32 75852 69617 33 34 35 52672 95714 53846 36 60306 37 50265 38 39 63613 64784 82319 60688 40 41 42 43 80655 44 45 46 76567 47 48 49 50 76243 51 52 53 60308 54 55 56 57 ...
result:
ok correct
Test #19:
score: -100
Runtime Error
input:
100 456 0.123000 44 456 0.123000 0 456 0.123000 9 456 0.123000 10 456 0.123000 95 456 0.123000 100 456 0.123000 53 456 0.123000 37 456 0.123000 37 456 0.123000 42 456 0.123000 40 456 0.123000 4 456 0.123000 47 456 0.123000 4 456 0.123000 84 456 0.123000 71 456 0.123000 83 456 0.123000 2 456 0.123000...