QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #79910 | #5402. 术树数 | MoQz | 0 | 1739ms | 11768kb | C++ | 2.3kb | 2023-02-21 10:52:56 | 2023-02-21 10:53:00 |
Judging History
answer
#include<iostream>
#include<cstdio>
using namespace std;
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fod(i,a,b) for(int i=a;i>=b;--i)
#define ll long long
int read(){
int u=0;
char c=getchar();
while(c>'9'||c<'0')c=getchar();
while(c>='0'&&c<='9'){
u=u*10+c-48;
c=getchar();
}
return u;
}
int q,K,m,er[30],n=1;
int gcd(int x,int y){
if(!y)return x;
return gcd(y,x%y);
}
int add(int x,int y){
int u=0;
fo(i,0,m-1){
u+=((x/er[i]%K)+(y/er[i]%K))%K*er[i];
}
return u;
}
int cf(int x,int y){
int u=0;
fo(i,0,m-1){
u+=((x/er[i]%K)*y%K+K)%K*er[i];
}
return u;
}
ll h=0;
pair<ll,ll> kgcd(ll x,ll y){
if(!y)return {h,0};
pair<ll,ll>u=kgcd(y,x%y);
return {u.second,u.first-u.second*(x/y)};
}
int B[33];
int fa[19][200011],deep[200011];
int c[200011];
void Ins(int x){
fod(i,m-1,0){
if(x/er[i]>0){
Ins(cf(x,K/gcd(x/er[i],K)));
break;
}
}
fod(i,m-1,0){
if(x/er[i]>0){
if(!B[i]){
B[i]=x;
return ;
}
while(x/er[i]>0){
int u=(B[i]/er[i])/(x/er[i]),v=0;
v=add(B[i],cf(x,-u));
B[i]=x,x=v;
}
if(K%(B[i]/er[i])!=0){
h=gcd(K,B[i]);
pair<ll,ll>u=kgcd(B[i],K);
u.first%=K;
B[i]=cf(B[i],u.first);
}
}
}
}
int find(int x,int y){
if(deep[x]<deep[y])swap(x,y);
fod(i,18,0){
if(deep[fa[i][x]]>=deep[y])x=fa[i][x];
}
if(x==y)return x;
fod(i,18,0){
if(fa[i][x]&&fa[i][x]!=fa[i][y])
x=fa[i][x],y=fa[i][y];
}
return fa[0][x];
}
int main(){
q=read();
K=read();
m=read();
er[0]=1;
fo(i,1,m)er[i]=er[i-1]*K;
deep[1]=1;
while(q){
--q;
int opt=read();
if(opt==1){
int x=read(),v=read();
fa[0][++n]=x;
fo(i,1,18)fa[i][n]=fa[i-1][fa[i-1][n]];
deep[n]=deep[x]+1;
c[n]=add(c[x],v);
Ins(cf(v,2));
}
if(opt==2){
int x=read(),y=read(),v=read();
int lca=find(x,y),u=0;
fo(i,0,m-1){
u+=((c[x]/er[i]%K)+(c[y]/er[i]%K)+(v/er[i]%K)-(c[lca]/er[i]%K)+K)%K*er[i];
}
Ins(u);
}
if(opt==3){
int x=read(),y=read();
int lca=find(x,y),u=0;
fo(i,0,m-1){
u+=((c[x]/er[i]%K)+(c[y]/er[i]%K)-(c[lca]/er[i]%K)+K)%K*er[i];
}
fod(i,m-1,0){
if(B[i]){
int v=(u/er[i]%K)/(B[i]/er[i]);
u=add(u,cf(B[i],v));
}
}
printf("%lld\n",u);
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3624kb
input:
30 7 3 1 1 301 1 1 236 1 2 278 3 2 4 3 2 4 2 1 4 265 1 1 242 1 4 278 1 6 337 3 2 3 2 5 7 304 2 5 6 34 1 4 178 3 6 7 3 5 7 3 1 4 1 1 178 3 3 4 3 1 6 3 3 4 2 6 7 131 1 1 213 3 1 3 2 3 10 11 3 4 6 2 5 9 169 1 6 9 2 5 10 29 1 9 111 3 9 11
output:
91 91 296 135 156 57 114 218 114 51 203 154
result:
wrong answer 1st lines differ - expected: '0', found: '91'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Wrong Answer
Test #21:
score: 0
Wrong Answer
time: 1447ms
memory: 11768kb
input:
198517 3 16 1 1 40710744 1 2 21885097 1 1 23592366 1 4 7387074 1 5 16074177 1 1 41027400 1 4 18082971 1 2 12822448 1 1 2286557 1 1 27896295 1 11 14532760 1 8 2357296 1 11 9190559 1 6 40503152 3 4 11 3 1 7 3 3 7 3 8 14 3 12 15 3 2 3 1 10 34606866 1 13 42718465 1 16 30353561 3 5 11 3 2 6 3 16 18 1 3 2...
output:
19143742 28246604 25274775 14092338 4035466 1870249 25996870 39043405 39457492 20842597 21813869 555385 16618089 28632150 23716506 40085293 23466024 16278132 27052946 42689884 40280029 16108799 32980606 35380362 33770782 39606074 24594078 39954590 24619093 35563774 18942827 18305479 7159866 34246980...
result:
wrong answer 1st lines differ - expected: '0', found: '19143742'
Subtask #4:
score: 0
Memory Limit Exceeded
Test #26:
score: 0
Memory Limit Exceeded
input:
198891 26426880 1 1 1 0 2 1 2 0 3 1 2 1 1 0 3 2 3 3 1 2 1 2 0 1 2 0 1 3 0 1 6 0 2 1 6 0 2 3 6 0 3 2 3 1 2 13213440 1 2 13213440 1 4 13213440 3 4 10 1 1 13213440 2 3 4 0 2 3 8 13213440 1 1 0 1 12 0 1 13 0 1 3 0 3 2 11 3 2 12 2 11 14 13213440 1 6 0 2 12 14 0 2 1 2 0 1 10 0 1 12 0 2 3 13 0 3 12 14 3 1 ...
output:
0 0 0 0 13213440 13213440 0 0 0 13213440 0 0 13213440 0 13213440 0 13213440 0 13213440 13213440 13213440 13213440 13213440 0 13213440 13213440 0 13213440 13213440 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
result:
Subtask #5:
score: 0
Wrong Answer
Test #30:
score: 0
Wrong Answer
time: 1739ms
memory: 9016kb
input:
199458 2 25 1 1 31252443 2 1 2 22827339 1 2 13517756 1 2 5635412 1 3 33397078 1 3 33542998 2 3 5 1484991 3 5 6 2 1 3 7938846 2 1 2 3665458 1 3 29150948 3 4 5 1 3 733545 1 7 4698781 1 7 21699192 1 6 10854390 3 3 8 3 4 8 1 2 6889338 2 1 12 27646676 2 6 8 24407215 1 11 20847453 3 4 13 1 6 16891344 3 4 ...
output:
17880679 3831541 733545 2617123 2207964 2617123 880278 438986 257306 576472 109525 61295 102397 66323 82781 44411 102276 17558 66887 66887 0 83739 17240 17240 124168 67691 66798 9745 33204 20400 35690 50753 19350 50792 609 34061 1957 108 17261 201 1411 702 769 302 32 636 498 358 176 115 126 149 184 ...
result:
wrong answer 1st lines differ - expected: '150016', found: '17880679'
Subtask #6:
score: 0
Wrong Answer
Test #33:
score: 0
Wrong Answer
time: 41ms
memory: 6760kb
input:
49958 1023 2 1 1 122428 1 1 917186 2 2 3 53148 1 3 876461 2 1 3 968146 2 2 4 569341 2 3 4 199413 2 1 4 238371 1 3 127427 1 2 887225 2 1 4 776059 2 4 6 155479 2 1 6 795533 1 5 159578 3 5 6 2 2 5 758778 2 5 6 601115 3 4 7 1 4 202224 2 5 6 902346 3 1 6 3 5 7 3 3 5 1 2 791251 1 5 502214 2 6 7 929048 1 6...
output:
964761 1016056 971362 311377 1040951 11691 787244 345179 423046 655058 309773 416445 300045 68204 449763 996908 996908 203937 15955 444062 38443 283867 917788 45213 445394 481297 819270 728292 423046 385811 169222 775863 661043 271006 205843 314774 1015884 795060 356553 417870 1040951 564773 988546 ...
result:
wrong answer 1st lines differ - expected: '0', found: '964761'
Subtask #7:
score: 0
Skipped
Dependency #1:
0%