QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#696835#9532. 长野原龙势流星群tosivan0 244ms74356kbC++141.8kb2024-11-01 03:01:102024-11-01 03:01:10

Judging History

你现在查看的是最新测评结果

  • [2024-11-01 03:01:10]
  • 评测
  • 测评结果:0
  • 用时:244ms
  • 内存:74356kb
  • [2024-11-01 03:01:10]
  • 提交

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%