QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#874306 | #8127. Slučajna Cesta | Unforgettablepl | 0 | 31ms | 12516kb | C++20 | 2.6kb | 2025-01-27 23:11:48 | 2025-01-27 23:11:49 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
template <int MOD=1000000007>
struct Modular {
int value;
static const int MOD_value = MOD;
Modular(long long v = 0) { value = v % MOD; if (value < 0) value += MOD;}
Modular(long long a, long long b) : value(0){ *this += a; *this /= b;}
Modular& operator+=(Modular const& b) {value += b.value; if (value >= MOD) value -= MOD; return *this;}
Modular& operator-=(Modular const& b) {value -= b.value; if (value < 0) value += MOD;return *this;}
Modular& operator*=(Modular const& b) {value = (long long)value * b.value % MOD;return *this;}
friend Modular mexp(Modular a, long long e) {
Modular res = 1; while (e) { if (e&1) res *= a; a *= a; e >>= 1; }
return res;
}
friend Modular inverse(Modular a) { return mexp(a, MOD - 2); }
Modular& operator/=(Modular const& b) { return *this *= inverse(b); }
friend Modular operator+(Modular a, Modular const b) { return a += b; }
friend Modular operator-(Modular a, Modular const b) { return a -= b; }
friend Modular operator-(Modular const a) { return 0 - a; }
friend Modular operator*(Modular a, Modular const b) { return a *= b; }
friend Modular operator/(Modular a, Modular const b) { return a /= b; }
friend std::ostream& operator<<(std::ostream& os, Modular const& a) {return os << a.value;}
friend bool operator==(Modular const& a, Modular const& b) {return a.value == b.value;}
friend bool operator!=(Modular const& a, Modular const& b) {return a.value != b.value;}
};
int32_t main(){
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int n;
cin >> n;
vector<vector<int>> adj(n+1);
for(int i=1;i<n;i++){
int p;
cin >> p;
adj[i+1].emplace_back(p);
adj[p].emplace_back(i+1);
}
vector<Modular<>> v(n+1);
for(int i=1;i<=n;i++){
int a;cin>>a;
v[i]=a;
}
vector<Modular<>> Expr(n+1);
{
Modular<> power = 1;
for(int i=1;i<=n;i++){
Expr[i]=(power-1)/(power*(i-1));
power*=2;
}
}
vector<Modular<>> Scores(n+1);
function<void(int,int)> dfs = [&](int x,int p){
Scores[x] = v[x];
for(int&j:adj[x])if(j!=p){
dfs(j,x);
Scores[x] += Scores[j]*Expr[adj[x].size()];
}
};
dfs(1,0);
vector<Modular<>> ans(n+1);
function<void(int,int,Modular<>)> dfs2 = [&](int x,int p,Modular<> s){
ans[x]=v[x]+s*Expr[adj[x].size()+1];
for(int&j:adj[x])if(j!=p){
ans[x]+=Scores[j]*Expr[adj[x].size()+1];
};
for(int&j:adj[x])if(j!=p){
dfs2(j,x,ans[x]-Scores[j]*Expr[adj[x].size()+1]);
};
};
dfs2(1,0,0);
for(int i=1;i<=n;i++)cout<<ans[i]<<'\n';
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 10
Accepted
time: 1ms
memory: 3712kb
input:
2 1 307903 536004
output:
575905 500689959
result:
ok all correct
Test #2:
score: 5
Acceptable Answer
time: 1ms
memory: 3584kb
input:
3 1 2 992649 690492 637324
output:
1497226 876301738 188668693
result:
points 0.50 the answer of the first question is correct, but there are mistakes in other answers.
Test #3:
score: 0
Wrong Answer
time: 1ms
memory: 3584kb
input:
4 1 2 3 826918 524416 30987 233038
output:
501126006 889825 344181320 547280006
result:
wrong output format Extra information in the output file
Subtask #2:
score: 0
Wrong Answer
Test #23:
score: 0
Wrong Answer
time: 1ms
memory: 3584kb
input:
100 1 2 1 4 5 6 7 7 9 9 5 12 5 4 1 16 17 18 18 20 20 22 23 24 25 23 27 28 27 30 31 32 27 34 35 36 37 38 39 39 41 38 43 43 45 46 43 48 49 49 49 48 48 54 55 56 57 57 55 60 60 62 55 64 65 64 67 67 69 69 69 72 37 74 75 76 76 78 76 80 81 82 80 84 85 74 87 87 89 89 91 89 87 94 94 96 97 98 98 754341 720186...
output:
744419112 92458129 796633776 906713019 738813483 44634543 257542414 899681876 998420397 604089252 437373227 966752781 233425519 994847799 870642959 718590095 864717787 487021558 660446535 552956953 526593760 265808098 653590496 456641011 500338841 750980871 168567006 320979429 98218861 659253483 842...
result:
wrong output format Extra information in the output file
Subtask #3:
score: 0
Wrong Answer
Test #54:
score: 0
Wrong Answer
time: 30ms
memory: 8960kb
input:
60000 1 2 2 1 3 4 5 6 9 6 11 11 13 8 4 10 7 10 3 16 12 9 19 15 24 24 27 25 8 16 13 7 20 15 22 28 33 31 20 27 41 17 25 35 39 5 22 34 19 14 49 34 51 31 39 56 55 48 48 14 47 50 58 12 61 41 66 21 62 64 57 32 54 30 30 50 45 40 56 38 38 43 76 44 84 49 59 84 66 45 57 60 47 42 33 54 74 37 59 26 18 101 80 67...
output:
117639703 390818501 202713296 694335166 734075415 131054207 136423330 920754578 460887682 541621383 782453778 709935982 911110370 807737023 341035751 87442579 445030156 235342255 33841054 221704533 73327605 425614210 857691168 55928611 708755485 412927905 131522540 559598816 628788432 235824959 9235...
result:
wrong output format Extra information in the output file
Subtask #4:
score: 0
Wrong Answer
Test #79:
score: 0
Wrong Answer
time: 31ms
memory: 12516kb
input:
100000 1 1 3 4 5 6 7 8 9 10 9 12 13 14 15 14 12 8 19 20 21 20 19 24 24 26 26 28 29 26 31 26 33 34 26 36 36 38 39 40 41 36 4 44 45 46 47 47 49 44 51 52 53 54 53 52 57 58 59 60 61 61 63 61 65 66 67 67 69 70 69 72 59 74 74 76 76 78 79 78 81 82 83 84 85 82 87 87 58 90 91 92 93 91 95 51 97 98 99 99 101 1...
output:
736079324 493813535 376635493 516986516 590942249 525090797 959170558 814024029 725013570 506463223 878670023 152138435 740433723 388810643 592237351 984236875 173984823 367870467 985865808 76631616 287253098 831447523 726533382 247225719 478143261 782915699 512674554 144579184 421421893 523244990 5...
result:
wrong output format Extra information in the output file