QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#187914 | #6561. Fail Fast | Feet_McYeet | WA | 142ms | 35136kb | C++20 | 3.9kb | 2023-09-25 06:06:03 | 2023-09-25 06:06:05 |
Judging History
answer
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <array>
#include <iterator>
#include <algorithm>
#include <bit>
#include <numeric>
#include <iomanip>
#include <stack>
using namespace std;
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
#define el << '\n'
#define nl cout << '\n'
#define cina(a,n) for (int i=0; i<n; i++) cin >> a[i]
#define ll long long
#define spc << ' '
#define forn(i,n) for (int i=0; i<n; i++)
#define forl(i,s,e) for (int i=s; i<e; i++)
#define pb push_back
#define ansyes cout << "YES\n"
#define ansno cout << "NO\n"
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pss pair<short, short>
#define MAX *max_element
#define MIN *min_element
#define rsz resize
#define sz(x) ((int) x.size())
#define all(x) x.begin(), x.end()
#define bsi(x, v) (int) (lower_bound(x.begin(), x.end(), v) - x.begin());
const int inf = 1000000000;
const ll inf2 = 4000000000000000000;
const int MAXN = 100005;
struct node {
long double c;
long double p;
int o;
};
bool operator < (const node& n1, const node& n2) {
return n1.c*(1-n2.p) > n2.c*(1-n1.p);
}
bool operator == (const node& n1, const node& n2) {
return n1.c==n2.c && n1.p==n2.p && n1.o==n2.o;
}
int par[MAXN];
int dep[MAXN];
void join(int a, int b) {
if (dep[a]>dep[b]) swap(a,b);
par[b] = a;
}
int g(int cn) {
if (par[cn] == cn) return cn;
par[cn] = g(par[cn]);
return par[cn];
}
int p[MAXN];
vector<int> ch[MAXN];
vector<int> cm[MAXN];
vector<int> cdm[MAXN];
void dfs(int cn, int d) {
dep[cn] = d;
for (int i : ch[cn]) dfs(i, d+1);
}
node re[MAXN];
priority_queue<node> pq;
void dfs2(int cn) {
cout << cn+1 el;
for (int i : cdm[cn]) {
pq.push(re[i]);
}
for (int i : cm[cn]) {
dfs2(i);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n; cin >> n;
forn(i,n) {
par[i] = i;
}
forn(i,n) {
cin >> re[i].c >> re[i].p >> p[i];
p[i]--;
re[i].o = i;
pq.push(re[i]);
if (p[i] != -1) ch[p[i]].pb(i);
}
// forn(i,n) {
// cout << i spc << re[i].c spc << re[i].p el;
// }
forn(i,n) if (p[i]==-1) dfs(i, 0);
bool v2[n];
forn(i,n) v2[i] = false;
while (sz(pq)) {
// cout << sz(pq) << endl;
node temp = pq.top();
pq.pop();
if (!(re[temp.o] == temp)) continue;
if (p[temp.o] == -1) continue;
if (v2[temp.o]) continue;
v2[temp.o] = true;
// cout << temp.o spc << temp.c spc << temp.p spc << re[temp.o].c spc << re[temp.o].p el;
int pa = g(p[temp.o]);
if (re[pa] < temp) {
re[pa].c += re[pa].p * temp.c;
re[pa].p *= temp.p;
cm[p[temp.o]].pb(temp.o);
pq.push(re[pa]);
join(pa, temp.o);
}
}
forn(i,n) {
vector<int> temp;
temp.rsz(sz(cm[i]));
forn(j,sz(cm[i])) temp[j] = cm[i][j];
sort(all(temp));
sort(all(ch[i]));
int a = 0, b = 0 ;
forn(k, sz(temp)+sz(ch[i])) {
if (b == sz(temp)) {
cdm[i].pb(ch[i][a]);
a++;
continue;
}
if (ch[i][a] == temp[b]) {
a++; b++; k++;
continue;
}
cdm[i].pb(ch[i][a]);
a++;
}
}
forn(i,n) if (p[i]==-1) pq.push(re[i]);
// forn(i,n) if (sz(cm[i])) cout << i spc;
// nl;
// forn(i,n) if (!sz(cm[i])) cout << i spc;
// nl;
while (sz(pq)) {
int temp = pq.top().o;
pq.pop();
dfs2(temp);
}
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 11776kb
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: 2ms
memory: 11876kb
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: 0ms
memory: 10632kb
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: 2ms
memory: 11800kb
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: 10632kb
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 19 20 17 11 1 4 5 8 14 18 9 15 3 12
result:
ok correct
Test #6:
score: 0
Accepted
time: 3ms
memory: 11880kb
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: 12488kb
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: 11408kb
input:
1 10 0.5 0
output:
1
result:
ok correct
Test #9:
score: 0
Accepted
time: 2ms
memory: 11840kb
input:
2 100 0.8 0 200 0.7 0
output:
1 2
result:
ok correct
Test #10:
score: 0
Accepted
time: 2ms
memory: 11940kb
input:
2 10 0.5 0 5 0.4 1
output:
1 2
result:
ok correct
Test #11:
score: 0
Accepted
time: 0ms
memory: 12528kb
input:
2 1000 0.7 2 1 0.6 0
output:
2 1
result:
ok correct
Test #12:
score: 0
Accepted
time: 111ms
memory: 31164kb
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: 56ms
memory: 29944kb
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: 142ms
memory: 35136kb
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: 135ms
memory: 24692kb
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: -100
Wrong Answer
time: 115ms
memory: 24704kb
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 2754 5745 5840 61325 61426 70 4349 739 5234 10413 2679 10128 14274 79762 30407 92693 98817 35 1243 11751 49724 94468 28424 41338 220 4584 702 10034 40074 1056 32441 28243 3 6 12 9550 123 1113 15255 26543 1657 3838 31...
result:
wrong answer your plan is not optimal