QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#696835 | #9532. 长野原龙势流星群 | tosivan | 0 | 244ms | 74356kb | C++14 | 1.8kb | 2024-11-01 03:01:10 | 2024-11-01 03:01:10 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
const ll INF=1e18;
ll val[200005];
struct Line{
ll m,c,pt;
bool operator<(const Line& l)const{
if(pt!=l.pt)return pt<l.pt;
if(m!=l.m)return m<l.m;
return c<l.c;
}
};
struct Info{
multiset<Line>ms;
void add(ll m, ll c, ll pt){
if(ms.size()==0){ms.insert({m,c,pt});return;}
Line lol=*ms.rbegin();
if(lol.pt<pt){ms.insert({m,c,pt});return;}
lol=*ms.lower_bound({-INF,-INF,pt});
if(pt!=lol.pt){ms.insert({m,c,pt});return;}
lol.m+=m; lol.c+=c;
ms.insert(lol);
}
ll balance(){
ll m=0,c=0;
while(ms.size()){
Line lol=*ms.rbegin();
m+=lol.m,c+=lol.c;
ms.erase(ms.find(lol));
ll x;
if(ms.size()==0){
x=(-c)/m;
ms.insert({m,c,x}); return x;
}
else{
Line finale=*ms.rbegin();
ll x=finale.pt+1;
if(m*x+c>=0){
x=(-c)/m;
ms.insert({m,c,x}); return x;
}
}
}
Line lol=*ms.rbegin(); return lol.pt;
}
ll size(){
return ms.size();
}
};
vector<ll>adj[200005];
Info ms[200005];
ll ans[200005];
void merge(ll a, ll b){
if(ms[a].size()<ms[b].size())swap(ms[a],ms[b]);
for(auto& k: ms[b].ms){
ms[a].add(k.m,k.c,k.pt);
}
}
void dfs(ll s){
for(auto& u: adj[s]){
dfs(u);
merge(s,u);
}
ms[s].add(-1,val[s],INF);
ans[s]=ms[s].balance();
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll n;
cin>>n;
for(int i=2;i<=n;i++){
ll k;
cin>>k;
adj[k].push_back(i);
}
for(int i=1;i<=n;i++)cin>>val[i];
for(int i=1;i<=n;i++){
val[i]*=(10000000LL);
}
dfs(1);
for(int i=1;i<=n;i++){
ld bruh=ans[i];
cout<<fixed<<setprecision(10)<<bruh/10000000<<'\n';
}
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 10
Accepted
time: 3ms
memory: 19040kb
input:
2000 1 2 2 4 5 2 3 6 4 2 7 2 8 14 8 12 1 14 4 14 8 18 9 2 7 22 20 22 14 29 28 16 6 21 23 6 21 14 13 9 1 4 18 13 2 39 21 33 18 20 38 27 27 1 49 5 51 3 31 24 10 42 2 44 13 9 35 66 27 60 67 59 29 40 53 2 33 43 26 43 62 16 78 45 14 10 73 69 41 35 25 26 2 70 54 1 54 48 5 36 44 28 90 29 51 51 93 82 95 45 ...
output:
883838885.9230769000 887174926.0000000000 881025216.7096774000 912609654.6666666000 872318573.5000000000 831791515.1538461000 867874850.0000000000 892392319.1666666000 836427216.0000000000 869519853.8000000000 693335785.3750000000 925100890.0000000000 994728511.5000000000 950304719.0000000000 808673...
result:
ok 2000 numbers
Test #2:
score: 10
Accepted
time: 5ms
memory: 18828kb
input:
2000 1 1 1 1 1 6 6 6 8 1 7 6 9 4 11 10 17 1 9 20 4 2 7 22 13 21 5 26 19 20 9 8 24 22 32 24 24 8 30 7 22 22 7 14 4 18 30 38 9 45 21 38 53 16 39 6 44 12 10 34 14 17 54 14 65 55 17 21 40 9 27 65 54 53 61 30 3 52 57 49 31 34 16 32 11 85 81 43 36 43 3 45 42 93 83 37 86 77 2 23 41 77 19 18 51 91 68 22 85 ...
output:
794920955.2200000000 713825019.5000000000 734115991.8000000000 800547209.7837837000 734508347.0000000000 760946433.3750000000 750093634.8979591000 735976830.1111111000 765501191.9411764000 747665901.9523809000 816306482.5000000000 741938108.1111111000 790936468.7500000000 784791287.9047619000 686615...
result:
ok 2000 numbers
Test #3:
score: 10
Accepted
time: 0ms
memory: 20596kb
input:
2000 1 1 2 3 3 3 3 4 2 8 4 6 2 10 1 8 8 13 1 19 15 18 8 17 20 16 16 21 11 28 14 18 31 4 30 24 17 10 22 26 2 34 14 13 13 37 43 3 3 38 9 4 29 43 29 46 7 55 9 23 23 49 29 12 45 25 67 59 45 24 5 55 52 73 51 28 25 26 49 78 62 10 18 1 35 73 35 16 52 62 5 89 4 49 12 46 55 14 18 68 64 25 21 88 25 19 82 46 4...
output:
755177543.5161290000 762060513.2941176000 754126791.2625000000 777333185.5500000000 758703127.5000000000 756576527.2222222000 764146306.7857142000 750062914.1400000000 710728919.8125000000 770351278.7500000000 769495170.0000000000 776873566.5714285000 763361472.6000000000 718961316.4545454000 691159...
result:
ok 2000 numbers
Test #4:
score: 10
Accepted
time: 5ms
memory: 19012kb
input:
2000 1 1 3 4 1 1 4 3 3 2 1 3 11 3 1 7 17 9 7 18 4 5 16 10 16 14 12 6 16 22 28 32 27 4 4 19 36 38 12 31 28 18 30 44 35 43 44 29 10 29 7 18 18 35 23 42 12 24 23 2 42 59 8 24 14 49 16 62 38 46 7 34 41 41 10 20 53 71 18 38 63 54 26 76 39 84 28 36 9 53 26 19 39 34 26 49 86 10 64 34 74 43 19 70 97 35 92 4...
output:
914894038.5333333000 918141155.8333333000 911927555.0000000000 870659540.1538461000 777969562.2352941000 778920774.5555555000 876560725.0000000000 974455318.0000000000 858643515.2500000000 835985850.6190476000 963419161.2500000000 868819817.0000000000 813378295.0000000000 984875621.0000000000 762109...
result:
ok 2000 numbers
Test #5:
score: 10
Accepted
time: 3ms
memory: 20564kb
input:
2000 1 2 2 3 2 1 7 8 8 6 9 12 12 3 8 3 9 15 3 19 8 7 4 19 18 23 10 21 10 15 10 22 1 21 19 26 1 38 38 1 18 37 14 27 37 43 30 4 2 2 13 42 13 9 13 38 21 23 58 32 13 62 18 62 15 49 5 61 1 45 29 48 38 34 31 43 45 38 52 54 13 21 78 36 21 45 57 14 25 18 29 45 2 43 8 51 75 79 95 55 29 98 55 93 33 5 93 14 77...
output:
865975765.9540229000 864960665.6000000000 853815173.5555555000 725289681.8000000000 835914002.7500000000 751151162.3000000000 880779494.2631578000 883843482.9166666000 866946310.4600000000 875695250.2727272000 798984107.4000000000 869102654.8928571000 879836598.4166666000 911092097.0000000000 850227...
result:
ok 2000 numbers
Test #6:
score: 10
Accepted
time: 0ms
memory: 20576kb
input:
2000 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...
output:
780031265.2857142000 709196423.6341463000 852016017.0000000000 710198590.8550724000 942523004.0000000000 795582647.0000000000 817131607.0000000000 723247621.6750000000 711787456.3214285000 702698215.8181818000 778948304.7500000000 825829512.6666666000 731540545.6842105000 717838198.7250000000 755917...
result:
ok 2000 numbers
Test #7:
score: 10
Accepted
time: 5ms
memory: 18436kb
input:
2000 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...
output:
621161049.0487804000 460347579.9461538000 624970425.7239263000 386751620.2403100000 463913107.3178294000 565084289.9534883000 628866372.3798449000 344826388.2000000000 389755854.0156250000 428515994.7968750000 467520113.5312500000 517598544.1640625000 569478380.3046875000 614133627.3046875000 633756...
result:
ok 2000 numbers
Test #8:
score: 10
Accepted
time: 2ms
memory: 20424kb
input:
2000 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...
output:
621374004.5748792000 487030122.8750000000 624597241.7000000000 939364019.0000000000 480110389.2480620000 578610053.0000000000 628514468.2138364000 497600202.0000000000 398302285.6701030000 430778150.1788617000 483844086.0234375000 534427093.2698412000 585697877.2592592000 623651552.6739130000 634659...
result:
ok 2000 numbers
Test #9:
score: 10
Accepted
time: 6ms
memory: 18636kb
input:
2000 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...
output:
762088830.2333333000 781353370.1724137000 714336862.8333333000 723995695.1304347000 787379090.4642857000 708370854.0526315000 735529969.8260869000 725933828.3181818000 721088075.7380952000 810402666.8888888000 798070041.7142857000 761321868.0000000000 708379177.7407407000 806707103.0000000000 682416...
result:
ok 2000 numbers
Test #10:
score: 10
Accepted
time: 5ms
memory: 18616kb
input:
2000 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...
output:
796409562.0000000000 777105384.2500000000 719995401.8400000000 755696351.5238095000 972657380.0000000000 705728479.9464285000 822339463.6666666000 756514023.7142857000 858700663.0000000000 980362468.0000000000 924539106.0000000000 708454243.0000000000 722158127.3103448000 856914923.0000000000 691671...
result:
ok 2000 numbers
Test #11:
score: 10
Accepted
time: 0ms
memory: 20360kb
input:
2000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
984618295.6153846000 902277197.0000000000 383235589.0000000000 742640716.0000000000 613666672.0000000000 291453150.0000000000 625937043.0000000000 958739025.0000000000 34831727.0000000000 240997073.0000000000 334863696.0000000000 223278814.0000000000 111864227.0000000000 669195136.0000000000 1725111...
result:
ok 2000 numbers
Test #12:
score: 10
Accepted
time: 5ms
memory: 18680kb
input:
2000 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...
output:
506787773.3134328000 507473433.6541353000 508859284.1666666000 556160454.2500000000 620472531.0000000000 867793536.0000000000 786222333.0000000000 511025497.6808510000 532981265.4285714000 612986220.0000000000 767631955.6666666000 992646284.0000000000 966889609.0000000000 550282737.3333333000 558374...
result:
ok 2000 numbers
Test #13:
score: 0
Wrong Answer
time: 0ms
memory: 18848kb
input:
2000 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...
output:
63531611.2957746000 63753215.7738515000 63975178.0248226000 64198661.3701067000 64423167.2892857000 64648572.7168458000 64875333.7589928000 65102116.2202166000 65329580.8333333000 65555761.2290909000 65782265.9489051000 66004005.9157509000 66227005.5735294000 66448482.4317343000 66667707.0407407000 ...
result:
wrong answer 1st numbers differ - expected: '470231718.6965000', found: '63531611.2957746', error = '0.8648930'
Subtask #2:
score: 0
Wrong Answer
Test #32:
score: 10
Accepted
time: 244ms
memory: 74356kb
input:
200000 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52...
output:
792545632.4154929000 794937150.3513513000 794843085.4776119000 804131414.2264150000 805846267.1666666000 806376230.0000000000 778037203.6904761000 815562308.1500000000 776087995.6012658000 809328819.5882352000 767722826.5953757000 771619640.6969696000 800107654.4769230000 879639965.3333333000 775670...
result:
ok 200000 numbers
Test #33:
score: 0
Wrong Answer
time: 129ms
memory: 30528kb
input:
200000 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52...
output:
644143769.7333984000 630347535.5705939000 -200038498.1388428000 518319513.9512670000 -266664461.6534676000 645901486.4602076000 406566953.6435884000 460752659.0146341000 518825163.3073170000 576444990.5014634000 634186374.5014634000 646477651.8050682000 350728412.3924050000 378574282.5988315000 4068...
result:
wrong answer 1st numbers differ - expected: '647279839.4787689', found: '644143769.7333984', error = '0.0048450'
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #2:
0%