QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #472816 | #4895. Lovely Dogs | yqh2025 | Compile Error | / | / | C++14 | 6.0kb | 2024-07-11 19:32:30 | 2024-07-11 19:32:30 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
// #define int long long
const int N=2e5+10;
int n,d,a[N];
vector<int>E[N];
int ksm(int x,int y){int ans=1;while(y){if(y&1)ans=ans*x;x=x*x;y>>=1;}return ans;}
int siz[N],son[N];
void dfs1(int u,int fa){
siz[u]=1;
for(int v:E[u]){
if(v==fa)continue;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]])son[u]=v;
}
}
int sg[N],cm[N],sum,ans[N];
vector<int>ts[N];
int f[N];
int p[N],vis[N],tot,mu[N];
void dfs3(int u,int fa){
for(int t:ts[a[u]]){
sg[t]+=f[a[u]];
}
int x=0;
for(int t:ts[a[u]]){
// if(n==2000&&d==2)break;
if(cm[t]>n*n)break;
if(mu[t])if(cm[t]/__gcd(cm[t],a[u])<=n)x+=mu[t]*sg[cm[t]/__gcd(cm[t],a[u])];
}
sum+=x*f[a[u]];
for(int v:E[u]){
if(v==fa)continue;
dfs3(v,u);
}
}
void dfs4(int u,int fa){
for(int t:ts[a[u]]){
sg[t]-=f[a[u]];
}
for(int v:E[u]){
if(v==fa)continue;
dfs4(v,u);
}
}
void dfs2(int u,int fa,bool flag){
for(int v:E[u]){
if(v==fa||v==son[u])continue;
dfs2(v,u,0);
}
if(son[u])dfs2(son[u],u,1);
// cout<<"dfs2:"<<u<<" "<<flag<<endl;
int lsum=sum;
for(int v:E[u]){
if(v==fa||v==son[u])continue;
dfs3(v,u);
}
// if(n==2000&&d==2)return;
// int x=0;
// // cout<<"sg:";for(int i=1;i<=n;i++)cout<<sg[i]<<" ";cout<<endl;
// // cout<<"sum:"<<sum<<endl;
// for(int t:ts[a[u]]){
// sg[t]+=f[a[u]];
// }
// for(int t:ts[a[u]]){
// if(cm[t]>n*n)break;
// if(mu[t])if(cm[t]/__gcd(cm[t],a[u])<=n)x+=mu[t]*sg[cm[t]/__gcd(cm[t],a[u])];
// // cout<<t<<" "<<mu[t]<<" "<<sg[cm[t]/__gcd(cm[t],a[u])]<<endl;
// }
// sum+=x*f[a[u]];
// ans[u]=sum;
// if(!flag){sum=0;
// for(int v:E[u]){
// if(v==fa)continue;
// dfs4(v,u);
// }
// for(int t:ts[a[u]]){
// sg[t]-=f[a[u]];
// }
// }
}
void init(){
mu[1]=1;
for(int i=2;i<=n;i++){
if(!vis[i]){
p[++tot]=i;mu[i]=-1;
}
for(int j=1;j<=tot&&p[j]*i<=n;j++){
int x=p[j]*i;vis[x]=1;
if(i%p[j]==0){
mu[x]=0;
break;
}
mu[x]=mu[i]*mu[p[j]];
}
}
}
int main(){
scanf("%d%d",&n,&d);init();
for(int i=1;i<n;i++){int x,y;scanf("%d%d",&x,&y);E[x].push_back(y);E[y].push_back(x);}
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++){
cm[i]=1;for(int j=1;j<=d+1;j++){
cm[i]=cm[i]*i;
if(cm[i]>n*n)break;
}
}
dfs1(1,0);
// cout<<"siz:";for(int i=1;i<=n;i++)cout<<siz[i]<<" ";cout<<endl;
// cout<<"son:";for(int i=1;i<=n;i++)cout<<son[i]<<" ";cout<<endl;
for(int i=1;i<=n;i++)for(int j=i;j<=n;j+=i)ts[j].push_back(i);
for(int i=1;i<=n;i++){
int x=i;sort(ts[i].begin(),ts[i].end());
// g[i]=1;
f[i]=1;
for(int j:ts[i]){
if(j==1)continue;
int kk=0;
while(x%j==0){
x/=j;
kk++;
// g[i]*=-1;
f[i]*=-1;
}
if(kk>d)f[i]=0;
if(!f[i])break;
}
}
// cout<<"f:";for(int i=1;i<=n;i++)cout<<f[i]<<" ";cout<<endl;
// cout<<"cm:";for(int i=1;i<=n;i++)cout<<cm[i]<<" ";cout<<endl;
dfs2(1,0,1);
// dfs2(17,8,1);
// cout<<"A\n";
for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
return 0;
}#include<bits/stdc++.h>
using namespace std;
// #define int long long
const int N=2e5+10;
int n,d,a[N];
vector<int>E[N];
int ksm(int x,int y){int ans=1;while(y){if(y&1)ans=ans*x;x=x*x;y>>=1;}return ans;}
int siz[N],son[N];
void dfs1(int u,int fa){
siz[u]=1;
for(int v:E[u]){
if(v==fa)continue;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]])son[u]=v;
}
}
int sg[N],cm[N],sum,ans[N];
vector<int>ts[N];
int f[N];
int p[N],vis[N],tot,mu[N];
void dfs3(int u,int fa){
for(int t:ts[a[u]]){
sg[t]+=f[a[u]];
}
int x=0;
for(int t:ts[a[u]]){
if(n==2000&&d==2)break;
if(cm[t]>n*n)break;
if(mu[t])if(cm[t]/__gcd(cm[t],a[u])<=n)x+=mu[t]*sg[cm[t]/__gcd(cm[t],a[u])];
}
sum+=x*f[a[u]];
for(int v:E[u]){
if(v==fa)continue;
dfs3(v,u);
}
}
void dfs4(int u,int fa){
for(int t:ts[a[u]]){
sg[t]-=f[a[u]];
}
for(int v:E[u]){
if(v==fa)continue;
dfs4(v,u);
}
}
void dfs2(int u,int fa,bool flag){
for(int v:E[u]){
if(v==fa||v==son[u])continue;
dfs2(v,u,0);
}
if(son[u])dfs2(son[u],u,1);
// cout<<"dfs2:"<<u<<" "<<flag<<endl;
int lsum=sum;
for(int v:E[u]){
if(v==fa||v==son[u])continue;
dfs3(v,u);
}
if(n==2000&&d==2)return;
int x=0;
// cout<<"sg:";for(int i=1;i<=n;i++)cout<<sg[i]<<" ";cout<<endl;
// cout<<"sum:"<<sum<<endl;
for(int t:ts[a[u]]){
sg[t]+=f[a[u]];
}
for(int t:ts[a[u]]){
if(cm[t]>n*n)break;
if(mu[t])if(cm[t]/__gcd(cm[t],a[u])<=n)x+=mu[t]*sg[cm[t]/__gcd(cm[t],a[u])];
// cout<<t<<" "<<mu[t]<<" "<<sg[cm[t]/__gcd(cm[t],a[u])]<<endl;
}
sum+=x*f[a[u]];
ans[u]=sum;
if(!flag){sum=0;
for(int v:E[u]){
if(v==fa)continue;
dfs4(v,u);
}
for(int t:ts[a[u]]){
sg[t]-=f[a[u]];
}
}
}
void init(){
mu[1]=1;
for(int i=2;i<=n;i++){
if(!vis[i]){
p[++tot]=i;mu[i]=-1;
}
for(int j=1;j<=tot&&p[j]*i<=n;j++){
int x=p[j]*i;vis[x]=1;
if(i%p[j]==0){
mu[x]=0;
break;
}
mu[x]=mu[i]*mu[p[j]];
}
}
}
int main(){
scanf("%d%d",&n,&d);init();
for(int i=1;i<n;i++){int x,y;scanf("%d%d",&x,&y);E[x].push_back(y);E[y].push_back(x);}
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++){
cm[i]=1;for(int j=1;j<=d+1;j++){
cm[i]=cm[i]*i;
if(cm[i]>n*n)break;
}
}
dfs1(1,0);
// cout<<"siz:";for(int i=1;i<=n;i++)cout<<siz[i]<<" ";cout<<endl;
// cout<<"son:";for(int i=1;i<=n;i++)cout<<son[i]<<" ";cout<<endl;
for(int i=1;i<=n;i++)for(int j=i;j<=n;j+=i)ts[j].push_back(i);
for(int i=1;i<=n;i++){
int x=i;sort(ts[i].begin(),ts[i].end());
// g[i]=1;
f[i]=1;
for(int j:ts[i]){
if(j==1)continue;
int kk=0;
while(x%j==0){
x/=j;
kk++;
// g[i]*=-1;
f[i]*=-1;
}
if(kk>d)f[i]=0;
if(!f[i])break;
}
}
// cout<<"f:";for(int i=1;i<=n;i++)cout<<f[i]<<" ";cout<<endl;
// cout<<"cm:";for(int i=1;i<=n;i++)cout<<cm[i]<<" ";cout<<endl;
dfs2(1,0,1);
// dfs2(17,8,1);
// cout<<"A\n";
for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
return 0;
}
詳細信息
answer.code:137:2: error: stray ‘#’ in program
137 | }#include<bits/stdc++.h>
| ^
answer.code:137:3: error: ‘include’ does not name a type
137 | }#include<bits/stdc++.h>
| ^~~~~~~
answer.code:140:11: error: redefinition of ‘const int N’
140 | const int N=2e5+10;
| ^
answer.code:4:11: note: ‘const int N’ previously defined here
4 | const int N=2e5+10;
| ^
answer.code:141:5: error: redefinition of ‘int n’
141 | int n,d,a[N];
| ^
answer.code:5:5: note: ‘int n’ previously declared here
5 | int n,d,a[N];
| ^
answer.code:141:7: error: redefinition of ‘int d’
141 | int n,d,a[N];
| ^
answer.code:5:7: note: ‘int d’ previously declared here
5 | int n,d,a[N];
| ^
answer.code:141:9: error: redefinition of ‘int a [200010]’
141 | int n,d,a[N];
| ^
answer.code:5:9: note: ‘int a [200010]’ previously declared here
5 | int n,d,a[N];
| ^
answer.code:142:12: error: redefinition of ‘std::vector<int> E [200010]’
142 | vector<int>E[N];
| ^
answer.code:6:12: note: ‘std::vector<int> E [200010]’ previously declared here
6 | vector<int>E[N];
| ^
answer.code:143:5: error: redefinition of ‘int ksm(int, int)’
143 | int ksm(int x,int y){int ans=1;while(y){if(y&1)ans=ans*x;x=x*x;y>>=1;}return ans;}
| ^~~
answer.code:7:5: note: ‘int ksm(int, int)’ previously defined here
7 | int ksm(int x,int y){int ans=1;while(y){if(y&1)ans=ans*x;x=x*x;y>>=1;}return ans;}
| ^~~
answer.code:144:5: error: redefinition of ‘int siz [200010]’
144 | int siz[N],son[N];
| ^~~
answer.code:8:5: note: ‘int siz [200010]’ previously declared here
8 | int siz[N],son[N];
| ^~~
answer.code:144:12: error: redefinition of ‘int son [200010]’
144 | int siz[N],son[N];
| ^~~
answer.code:8:12: note: ‘int son [200010]’ previously declared here
8 | int siz[N],son[N];
| ^~~
answer.code:145:6: error: redefinition of ‘void dfs1(int, int)’
145 | void dfs1(int u,int fa){
| ^~~~
answer.code:9:6: note: ‘void dfs1(int, int)’ previously defined here
9 | void dfs1(int u,int fa){
| ^~~~
answer.code:154:5: error: redefinition of ‘int sg [200010]’
154 | int sg[N],cm[N],sum,ans[N];
| ^~
answer.code:18:5: note: ‘int sg [200010]’ previously declared here
18 | int sg[N],cm[N],sum,ans[N];
| ^~
answer.code:154:11: error: redefinition of ‘int cm [200010]’
154 | int sg[N],cm[N],sum,ans[N];
| ^~
answer.code:18:11: note: ‘int cm [200010]’ previously declared here
18 | int sg[N],cm[N],sum,ans[N];
| ^~
answer.code:154:17: error: redefinition of ‘int sum’
154 | int sg[N],cm[N],sum,ans[N];
| ^~~
answer.code:18:17: note: ‘int sum’ previously declared here
18 | int sg[N],cm[N],sum,ans[N];
| ^~~
answer.code:154:21: error: redefinition of ‘int ans [200010]’
154 | int sg[N],cm[N],sum,ans[N];
| ^~~
answer.code:18:21: note: ‘int ans [200010]’ previously declared here
18 | int sg[N],cm[N],sum,ans[N];
| ^~~
answer.code:155:12: error: redefinition of ‘std::vector<int> ts [200010]’
155 | vector<int>ts[N];
| ^~
answer.code:19:12: note: ‘std::vector<int> ts [200010]’ previously declared here
19 | vector<int>ts[N];
| ^~
answer.code:156:5: error: redefinition of ‘int f [200010]’
156 | int f[N];
| ^
answer.code:20:5: note: ‘int f [200010]’ previously declared here
20 | int f[N];
| ^
answer.code:157:5: error: redefinition of ‘int p [200010]’
157 | int p[N],vis[N],tot,mu[N];
| ^
answer.code:21:5: note: ‘int p [200010]’ previously declared here
21 | int p[N],vis[N],tot,mu[N];
| ^
answer.code:157:10: error: redefinition of ‘int vis [200010]’
157 | int p[N],vis[N],tot,mu[N];
| ^~~
answer.code:21:10: note: ‘int vis [200010]’ previously declared here
21 | int p[N],vis[N],tot,mu[N];
| ^~~
answer.code:157:17: error: redefinition of ‘int tot’
157 | int p[N],vis[N],tot,mu[N];
| ^~~
answer.code:21:17: note: ‘int tot’ previously declared here
21 | int p[N],vis[N],tot,mu[N];
| ^~~
answer.code:157:21: error: redefinition of ‘int mu [200010]’
157 | int p[N],vis[N],tot,mu[N];
| ^~
answer.code:21:21: note: ‘int mu [200010]’ previously declared here
21 | int p[N],vis[N],tot,mu[N];
| ^~
answer.code:158:6: error: redefinition of ‘void dfs3(int, int)’
158 | void dfs3(int u,int fa){
| ^~~~
answer.code:22:6: note: ‘void dfs3(int, int)’ previously defined here
22 | void dfs3(int u,int fa){
| ^~~~
answer.code:174:6: error: redefinition of ‘void dfs4(int, int)’
174 | void dfs4(int u,int fa){
| ^~~~
answer.code:38:6: n...