QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#808765#4229. GCD HarmonyTenshi#WA 8ms203244kbC++231.5kb2024-12-11 02:03:522024-12-11 02:03:53

Judging History

你现在查看的是最新测评结果

  • [2024-12-11 02:03:53]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:203244kb
  • [2024-12-11 02:03:52]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
 
#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
#define all(x) (x).begin(), (x).end()
 
#define x first
#define y second
using pii = pair<int, int>;
using ll = long long;
 
inline void read(int &x){
    int s=0; x=1;
    char ch=getchar();
    while(ch<'0' || ch>'9') {if(ch=='-')x=-1;ch=getchar();}
    while(ch>='0' && ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
    x*=s;
}

const int N=5050, M=N*2-10;

int f[N][M];
int n, w[N];
vector<int> g[N];

bool vis[M];
vector<int> d[M];

void init(int n){
	rep(i, 2, n){
		if(!vis[i]) d[i].pb(i);
		for(int j=i+i; j<=n; j+=i){
			vis[j]=true;
			if(!vis[i]) d[j].pb(i);
		}
	}
}

void dfs(int u, int fa){
	rep(i, 2, M-1) f[u][i]=(i==w[u]? 0: i);
	for(auto go: g[u]) if(go!=fa){
		dfs(go, u);
		rep(i, 2, M-1){	
			for(auto e: d[i]){
				f[u][i]+=f[go][e];
				f[u][i]=min(f[u][i], M);
			}
		}
	}
	rep(i, 2, M-1){
		for(int j=i+i; j<M; j+=i) f[u][i]=min(f[u][i], f[u][j]);
	}
}

void solve(){
	init(M-1);
	cin>>n;
	rep(i, 1, n) read(w[i]);
	
	rep(i, 1, n-1){
		int u, v; read(u), read(v);
		g[u].pb(v), g[v].pb(u);
	}	
	memset(f, 0x3f, sizeof f);
	dfs(1, 0);
	int res=2*n;
	rep(i, 2, M-1) res=min(res, f[1][i]);
	// rep(i, 2, M-1) debug(f[1][i]);
	cout<<res<<endl;
}

signed main(){
	solve();	
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 8ms
memory: 203244kb

input:

6
5
6
3
4
9
12
1 2
1 3
1 4
1 6
3 5

output:

6

result:

ok single line: '6'

Test #2:

score: 0
Accepted
time: 7ms
memory: 203216kb

input:

3
1
2
3
3 1
2 3

output:

4

result:

ok single line: '4'

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 203180kb

input:

13
2
5
5
5
5
5
5
3
3
3
3
3
3
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13

output:

21

result:

wrong answer 1st lines differ - expected: '15', found: '21'