QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #345662 | #4895. Lovely Dogs | zzafanti | 0 | 306ms | 205104kb | C++20 | 1.6kb | 2024-03-07 11:30:08 | 2024-03-07 11:30:10 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using E=long long;
int n,d;
vector<vector<int>> ver;
vector<int> a,w,sz,res;
vector<array<array<int,12>,20>> dp;
void dfs(int u,int fa=0){
int x=a[u],c1=0,c2=0;
while(x%2==0) x/=2,c1++;
while(x%3==0) x/=3,c2++;
array<array<int,12>,20> sum;
dp[u][c1][c2]=w[u];
sz[u]=(c1*2<=d&&c2*2<=d?1:0);
auto Sum=[&]()->void{
for(int i=0; i<20; i++){
for(int j=0; j<12; j++){
sum[i][j]=dp[u][i][j];
if(i) sum[i][j]+=sum[i-1][j];
if(j) sum[i][j]+=sum[i][j-1];
if(i&&j) sum[i][j]-=sum[i-1][j-1];
}
}
};
Sum();
E ans=0;
for(auto p:ver[u]){
if(p==fa) continue;
dfs(p,u);
res[u]+=res[p];
for(int i=0; i<20; i++){
for(int j=0; j<12; j++){
ans+=dp[p][i][j]*sum[min(19,d-i)][min(11,d-j)];
dp[u][i][j]+=dp[p][i][j];
}
}
Sum();
}
res[u]+=ans+sz[u];
}
int main(){
#ifdef zzafanti
freopen("in.in","r",stdin);
#endif // zzafanti
cin.tie(nullptr),cout.tie(nullptr)->sync_with_stdio(false);
cin>>n>>d; assert(d==20);
ver.resize(n+1); w.resize(n+1); res.resize(n+1);
a.resize(n+1); dp.resize(n+1); sz.resize(n+1);
for(int i=1; i<n; i++){
int y,x;
cin>>x>>y;
ver[x].emplace_back(y);
ver[y].emplace_back(x);
}
for(int i=1; i<=n; i++) cin>>a[i];
for(int t=1; t<=n; t++){
int x=a[t],cnt=0;
for(int i=2; i*i<=x; i++){
if(x%i) continue;
while(x%i==0) x/=i,cnt++;
}
if(x>1) cnt++;
w[t]=(cnt&1?-1:1);
}
dfs(1);
for(int i=1; i<=n; i++) cout<<res[i]<<'\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 0
Runtime Error
input:
20 2 18 8 18 11 13 19 10 8 9 11 4 8 9 15 9 17 2 1 13 18 20 18 1 8 12 17 7 16 5 11 16 15 6 19 14 16 1 3 2 15 5 13 20 6 16 18 9 19 17 7 14 10 11 3 1 12 4 8
output:
result:
Subtask #2:
score: 0
Runtime Error
Test #24:
score: 0
Runtime Error
input:
2000 1 134 1468 867 1750 351 1220 1690 1888 1685 134 585 282 1142 643 206 271 260 1833 1987 770 1029 1667 322 1371 341 518 601 915 119 893 1933 1502 951 1785 1056 1630 1957 1208 96 55 1508 1212 331 427 505 151 1378 1486 1545 697 1459 629 202 997 180 1917 1638 1177 1244 1896 302 658 1433 1605 1318 19...
output:
result:
Subtask #3:
score: 0
Memory Limit Exceeded
Test #45:
score: 10
Accepted
time: 294ms
memory: 205104kb
input:
200000 20 117994 12616 53490 106425 103660 50033 132640 78252 58384 19939 69183 10015 39098 165030 179856 130356 65245 57831 18234 83378 4240 154896 177149 102260 4634 180087 132390 19627 98506 60775 1890 120740 87908 21917 41323 192721 181885 96684 69412 139951 9800 38301 59025 29879 186185 81402 1...
output:
143459 1 6 1 17 19 1 2 3 1 1 26 1 1 1 1 1 1 7 1 1 3 1 2 1 1 1 1 4 3 2 1 3 13 19 1 1 1 1 1 1 34 1 1 1 12 1 1 3 1 24 1 1 1 2 1 1 6 1 3 1 3 1 10 1 1 1 3 4 9 1 2 3 1 1 1 7 2 6 1 1 1 1 1 1 2 3 457 2 1 3 1 1 1 1 12 1 1 1 6 2 1 1 3 1 3 113 1 4 11 2 1 4 2 1 1 1 25 22 2 3 1 1 3 3 1 2 3 1 2 1 1 107 1 1 14 1 1...
result:
ok 200000 tokens
Test #46:
score: 0
Accepted
time: 306ms
memory: 204964kb
input:
200000 20 26219 163867 20331 153212 126612 40599 53814 68996 79701 140933 144374 181902 59705 155221 11230 70725 158998 133605 163268 88141 83507 114091 7736 162046 143360 92662 197974 194981 129770 126237 133117 75376 44213 67464 131083 19290 35473 65770 192299 66427 112908 181240 139699 88439 1103...
output:
143459 1 1 3 3 1 4 1 1 1 17 2 4 2 1 1 1 1 2 1 1 1 2 1 1 1 9 1 2 2 1 1 1 1 2 1 1 3 1 2 7 1 1 1 1 1 3 6 14 20 1 1 1 7 7 1 52 1 6 1 1 24 5 3 3 1 1 1 1 1 12 1 1 16 1 1 4 1 1 1 1 9 1 1 1 1 1 5 1 1 120 1 22 1 1 1 4 15 1 3 3 1 1 1 1 48 1 1 1 1 1 1 13 1 3 3 1 1 7 1 5 3 1 1 1 1 1 1 1 783 3 1 1 1 1 2 1 1 1 1 ...
result:
ok 200000 tokens
Test #47:
score: -10
Memory Limit Exceeded
input:
200000 20 151436 178769 79211 141557 185103 181923 173473 84222 84222 31293 159673 17537 72335 131147 59289 141263 84222 23691 163353 84222 76461 84222 80651 84307 76526 12294 199619 84222 59457 177309 19912 1273 164867 44284 41990 26506 40399 84222 98264 145475 84222 48507 84222 88935 84222 176452 ...
output:
143459 94518 71442 82904 129477 42163 72542 1 1 45757 1 130757 52193 1 1 1 96408 1 78846 1 57773 1 1 1 86255 119507 1 1 83415 1 1 1 1 1 84437 1 1 1 72508 1 77107 84355 1 1 1 72616 52116 1 136452 1 100206 131528 1 146256 76408 1 1 1 1 50456 1 1 1 1 75137 1 83751 71005 116031 1 52173 1 75120 1 80850 1...
result:
Subtask #4:
score: 0
Runtime Error
Test #50:
score: 0
Runtime Error
input:
200000 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 26 1 27 1 28 1 29 1 30 1 31 1 32 1 33 1 34 1 35 1 36 1 37 1 38 1 39 1 40 1 41 1 42 1 43 1 44 1 45 1 46 1 47 1 48 1 49 1 50 1 51 1 52 1 53 1 54 1 55 1 56 1 57 1 58 1 59 1 60 1 61...
output:
result:
Subtask #5:
score: 0
Runtime Error
Test #55:
score: 0
Runtime Error
input:
200000 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 26 1 27 1 28 1 29 1 30 1 31 1 32 1 33 1 34 1 35 1 36 1 37 1 38 1 39 1 40 1 41 1 42 1 43 1 44 1 45 1 46 1 47 1 48 1 49 1 50 1 51 1 52 1 53 1 54 1 55 1 56 1 57 1 58 1 59 1 60 1 61...
output:
result:
Subtask #6:
score: 0
Runtime Error
Test #78:
score: 0
Runtime Error
input:
50000 1 8097 41839 17674 41774 40520 8024 5786 38261 20664 43471 1217 49276 11185 40807 14186 25584 31704 14814 42333 41475 13053 39565 45938 30104 5826 39463 5031 10814 43784 6042 58 33849 42978 18978 36307 33276 34769 4351 27884 37532 27528 29431 29451 39345 10946 9667 19016 47269 7911 30103 10308...
output:
result:
Subtask #7:
score: 0
Runtime Error
Test #103:
score: 0
Runtime Error
input:
200000 1 118863 188865 188022 168616 118976 119404 178852 33449 81624 40431 151228 160976 68943 136313 57200 117631 147789 139875 100240 55537 164811 145415 103548 186750 15010 168029 155731 107005 69836 1502 86171 122700 83448 131948 189162 94464 128210 2509 49724 183329 174782 192641 27687 71315 1...