QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #472829 | #4895. Lovely Dogs | yqh2025 | Compile Error | / | / | C++14 | 5.9kb | 2024-07-11 19:40:07 | 2024-07-11 19:40:07 |
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]];
}
}
}
signed main(){
scanf("%lld%lld",&n,&d);init();
for(int i=1;i<n;i++){int x,y;scanf("%lld%lld",&x,&y);E[x].push_back(y);E[y].push_back(x);}
for(int i=1;i<=n;i++)scanf("%lld",&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("%lld\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;
}
Details
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 long long int N’
140 | const int N=2e5+10;
| ^
answer.code:4:11: note: ‘const long long int N’ previously defined here
4 | const int N=2e5+10;
| ^
answer.code:141:5: error: redefinition of ‘long long int n’
141 | int n,d,a[N];
| ^
answer.code:5:5: note: ‘long long int n’ previously declared here
5 | int n,d,a[N];
| ^
answer.code:141:7: error: redefinition of ‘long long int d’
141 | int n,d,a[N];
| ^
answer.code:5:7: note: ‘long long int d’ previously declared here
5 | int n,d,a[N];
| ^
answer.code:141:9: error: redefinition of ‘long long int a [200010]’
141 | int n,d,a[N];
| ^
answer.code:5:9: note: ‘long long int a [200010]’ previously declared here
5 | int n,d,a[N];
| ^
answer.code:142:12: error: redefinition of ‘std::vector<long long int> E [200010]’
142 | vector<int>E[N];
| ^
answer.code:6:12: note: ‘std::vector<long long int> E [200010]’ previously declared here
6 | vector<int>E[N];
| ^
answer.code:143:5: error: redefinition of ‘long long int ksm(long long int, long long 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: ‘long long int ksm(long long int, long long 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 ‘long long int siz [200010]’
144 | int siz[N],son[N];
| ^~~
answer.code:8:5: note: ‘long long int siz [200010]’ previously declared here
8 | int siz[N],son[N];
| ^~~
answer.code:144:12: error: redefinition of ‘long long int son [200010]’
144 | int siz[N],son[N];
| ^~~
answer.code:8:12: note: ‘long long int son [200010]’ previously declared here
8 | int siz[N],son[N];
| ^~~
answer.code:145:6: error: redefinition of ‘void dfs1(long long int, long long int)’
145 | void dfs1(int u,int fa){
| ^~~~
answer.code:9:6: note: ‘void dfs1(long long int, long long int)’ previously defined here
9 | void dfs1(int u,int fa){
| ^~~~
answer.code:154:5: error: redefinition of ‘long long int sg [200010]’
154 | int sg[N],cm[N],sum,ans[N];
| ^~
answer.code:18:5: note: ‘long long int sg [200010]’ previously declared here
18 | int sg[N],cm[N],sum,ans[N];
| ^~
answer.code:154:11: error: redefinition of ‘long long int cm [200010]’
154 | int sg[N],cm[N],sum,ans[N];
| ^~
answer.code:18:11: note: ‘long long int cm [200010]’ previously declared here
18 | int sg[N],cm[N],sum,ans[N];
| ^~
answer.code:154:17: error: redefinition of ‘long long int sum’
154 | int sg[N],cm[N],sum,ans[N];
| ^~~
answer.code:18:17: note: ‘long long int sum’ previously declared here
18 | int sg[N],cm[N],sum,ans[N];
| ^~~
answer.code:154:21: error: redefinition of ‘long long int ans [200010]’
154 | int sg[N],cm[N],sum,ans[N];
| ^~~
answer.code:18:21: note: ‘long long int ans [200010]’ previously declared here
18 | int sg[N],cm[N],sum,ans[N];
| ^~~
answer.code:155:12: error: redefinition of ‘std::vector<long long int> ts [200010]’
155 | vector<int>ts[N];
| ^~
answer.code:19:12: note: ‘std::vector<long long int> ts [200010]’ previously declared here
19 | vector<int>ts[N];
| ^~
answer.code:156:5: error: redefinition of ‘long long int f [200010]’
156 | int f[N];
| ^
answer.code:20:5: note: ‘long long int f [200010]’ previously declared here
20 | int f[N];
| ^
answer.code:157:5: error: redefinition of ‘long long int p [200010]’
157 | int p[N],vis[N],tot,mu[N];
| ^
answer.code:21:5: note: ‘long long int p [200010]’ previously declared here
21 | int p[N],vis[N],tot,mu[N];
| ^
answer.code:157:10: error: redefinition of ‘long long int vis [200010]’
157 | int p[N],vis[N],tot,mu[N];
| ^~~
answer.code:21:10: note: ‘long long int vis [200010]’ previously declared here
21 | int p[N],vis[N],tot,mu[N];
| ^~~
answer.code:157:17: error: redefinition of ‘long long int tot’
157 | int p[N],vis[N],tot,mu[N];
| ^~~
answer.code:21:17: note: ‘long long int tot’ previously declared here
21 | int p[N],vis[N],tot,mu[N];
| ^~~
answer.code:157:21: error: redefinition of ‘long long int mu [200010]’
157 | int p[N],vis[N],tot,mu[N];
| ^~
answer.code:21:21: note: ‘long long int mu [200010]’ previously declared h...