QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#189298 | #6561. Fail Fast | ucup-team870 | AC ✓ | 147ms | 15644kb | C++14 | 1.7kb | 2023-09-27 09:19:03 | 2023-09-27 09:19:03 |
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 = 200010;
int d[N], fa[N], ans[N], cnt, tail[N], nxt[N], vis[N];
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) {
double s = c[a] * (1-p[b]), t = c[b] * (1-p[a]);
if (s == t) return a < b;
return s < t;
}
};
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) {
// cout <<"#";
int t = *s.begin();
s.erase(s.begin());
t = find(t);
// cout <<t<<"$$"<<endl;
// cout <<"$";
if (!vis[d[t]]) {
int f = find(d[t]);
// cout << f<<"#######"<<endl;
s.erase(s.find(f));
fa[t] = f;//cout <<"%";
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 {
// cout <<"#";
ans[++cnt] = t;
vis[t] = 1;
t = nxt[t];
} while (t);
}
}
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: 0ms
memory: 9832kb
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: 9656kb
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: 9836kb
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: 9768kb
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: 9892kb
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: 3ms
memory: 9704kb
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: 2ms
memory: 9836kb
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: 9588kb
input:
1 10 0.5 0
output:
1
result:
ok correct
Test #9:
score: 0
Accepted
time: 1ms
memory: 7792kb
input:
2 100 0.8 0 200 0.7 0
output:
1 2
result:
ok correct
Test #10:
score: 0
Accepted
time: 0ms
memory: 9776kb
input:
2 10 0.5 0 5 0.4 1
output:
1 2
result:
ok correct
Test #11:
score: 0
Accepted
time: 0ms
memory: 9812kb
input:
2 1000 0.7 2 1 0.6 0
output:
2 1
result:
ok correct
Test #12:
score: 0
Accepted
time: 139ms
memory: 14220kb
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: 45ms
memory: 15588kb
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: 49ms
memory: 15380kb
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: 130ms
memory: 15644kb
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: 112ms
memory: 15404kb
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: 112ms
memory: 15248kb
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: 131ms
memory: 15320kb
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: 0
Accepted
time: 0ms
memory: 9840kb
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...
output:
2 37 9 3 42 10 4 49 95 5 100 6 18 53 7 8 31 40 11 12 14 73 84 15 83 17 90 19 25 20 21 22 23 24 56 26 27 35 81 28 91 34 29 94 96 32 33 36 39 88 41 43 45 47 30 44 1 13 48 50 64 51 52 82 54 55 65 57 79 58 59 60 62 38 71 16 46 77 61 63 66 67 68 99 69 70 72 74 75 76 78 80 85 86 87 89 98 92 93 97
result:
ok correct
Test #20:
score: 0
Accepted
time: 123ms
memory: 15220kb
input:
100000 991626 0.995651 9504 995771 0.998261 79562 998060 0.995175 92360 992097 0.995626 3344 991954 0.991091 6502 995161 0.991812 89766 990581 0.996178 78414 991802 0.999306 97661 992640 0.995473 24083 994222 0.999294 89602 997968 0.992137 45379 993834 0.996958 76573 994607 0.993958 85053 995532 0.9...
output:
13200 75427 46826 91955 6792 58951 55107 91758 8159 83245 27728 84187 17052 32946 88578 39869 41072 87880 56112 29316 82758 58620 40149 45212 11072 78598 70427 16486 2563 43645 7366 11552 41031 13373 62192 83583 66503 67600 38542 75912 77272 84516 17222 19872 42647 62849 99825 22131 59316 54785 5510...
result:
ok correct
Test #21:
score: 0
Accepted
time: 80ms
memory: 15440kb
input:
100000 994360 0.971872 88920 993564 0.952659 41443 987411 0.953086 14489 985630 0.966869 48952 999079 0.962902 45554 992490 0.962228 48582 994303 0.999688 2207 981197 0.974874 89269 994427 0.954167 46810 982731 0.987444 19228 989277 0.968593 33423 992826 0.962838 21386 993938 0.981453 5429 989639 0....
output:
75696 30935 62149 9056 33005 89511 86903 50595 96461 51390 76049 88417 78266 66542 20035 92068 70310 90092 15209 55734 56807 74861 92709 65406 51172 94603 23029 69738 32661 26934 48828 3439 37047 20478 93906 33886 82412 19784 95442 62198 49432 14125 31214 38985 42167 65903 17693 52552 4677 87763 247...
result:
ok correct
Test #22:
score: 0
Accepted
time: 91ms
memory: 15312kb
input:
100000 985815 0.968338 16495 994819 0.979029 23173 991468 0.983509 81133 982365 0.950143 16314 983055 0.971887 62541 996806 0.971088 68267 995780 0.950299 74974 994532 0.955473 63606 989984 0.951905 81901 988566 0.998953 42305 996656 0.965468 55450 993573 0.994893 6634 997306 0.979634 16470 991636 0...
output:
13130 52362 46854 26229 51335 80347 86680 22539 74823 79936 77914 3081 32725 27753 33217 52760 95825 17422 58889 34274 49599 89422 71815 55768 83383 27789 86192 45722 41115 44524 29829 10847 62845 87416 49949 98368 61655 33583 36777 12533 97259 80536 19101 23746 98761 78888 51188 96827 62467 63281 6...
result:
ok correct
Test #23:
score: 0
Accepted
time: 85ms
memory: 15376kb
input:
100000 379221 0.374168 0 219097 0.093397 0 141258 0.041142 0 773286 0.353950 0 479988 0.960409 0 169530 0.061026 0 857709 0.406691 0 328582 0.276540 0 903160 0.739709 0 252384 0.785859 0 383381 0.117421 0 652923 0.378000 0 154387 0.849961 0 689248 0.502565 0 951646 0.417907 0 840656 0.173340 0 80522...
output:
27300 27976 10500 8980 9631 29827 42466 31708 41922 46188 34880 21131 40863 39318 44981 27847 20875 33333 3274 37915 36722 33972 39084 27339 46854 48282 27030 29281 32529 2079 30792 373 38419 47331 37775 36207 36950 10130 16372 14566 10655 3616 5900 45517 17417 38377 4372 24244 47165 11392 7150 1755...
result:
ok correct
Test #24:
score: 0
Accepted
time: 147ms
memory: 15644kb
input:
100000 210466 0.747974 14014 875274 0.741805 83670 213751 0.306945 37859 924462 0.720568 6619 216870 0.448922 14076 144128 0.273307 3318 191627 0.489542 94999 695166 0.745605 88175 700114 0.359530 1241 874007 0.041421 67065 715108 0.713048 65 400676 0.000343 41833 456908 0.421291 14481 51440 0.71410...
output:
12430 26046 74117 92942 79559 34874 33889 2103 30460 71222 55527 68745 16338 56243 84827 52383 28546 33572 27929 52035 50723 94922 13498 11155 5576 84171 30388 60198 35505 199 67796 31967 15488 12153 16903 96283 87999 99388 18362 68560 63993 39841 9243 309 9437 24831 14832 91149 42941 72482 64829 18...
result:
ok correct
Test #25:
score: 0
Accepted
time: 142ms
memory: 15428kb
input:
99856 576549 0.545246 0 430801 0.958125 0 987874 0.848851 0 783119 0.204964 0 855730 0.750672 0 310636 0.443476 0 237417 0.154278 0 78845 0.812317 0 285014 0.676250 0 525664 0.343623 0 950682 0.343284 0 522477 0.803923 0 397098 0.788337 0 837538 0.006097 0 348545 0.356729 0 509388 0.960808 0 544999 ...
output:
283 296 245 299 140 78 25 70 264 59 288 287 90407 200 63002 63003 182 165 177 72 305 224 53 41 28 231 239 308 76 315 71 179 146 106 24572 228 90722 29 166 52292 273 216 130 209 61 204 98 261 184 57962 133 267 156 286 81 188 304 52293 52294 51 119 85997 42 175 55127 7 2207 178 72767 56 17642 144 4536...
result:
ok correct
Test #26:
score: 0
Accepted
time: 1ms
memory: 9872kb
input:
5 10 0.5 0 1 0.5 1 1 0.5 1 9 0.5 0 1 0.5 4
output:
1 2 3 4 5
result:
ok correct