QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#626357 | #4229. GCD Harmony | nickbelov# | RE | 0ms | 0kb | C++20 | 3.0kb | 2024-10-10 05:29:44 | 2024-10-10 05:29:46 |
answer
#include <vector>
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T>
ostream_iterator<T> oit(const string &s = " "){ return ostream_iterator<T>(cout,s.c_str()); }
inline auto rep(int l, int r) { return views::iota(min(l, r), r); }
inline auto rep(int n) { return rep(0, n); }
inline auto rep1(int l, int r) { return rep(l, r + 1); }
inline auto rep1(int n) { return rep(1, n + 1); }
inline auto per(int l, int r) { return rep(l, r) | views::reverse; }
inline auto per(int n) { return per(0, n); }
inline auto per1(int l, int r) { return per(l, r + 1); }
inline auto per1(int n) { return per(1, n + 1); }
#define A(a) begin(a),end(a)
inline auto len = ranges::ssize;
struct chash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
template<typename T, typename U> using pb_map = gp_hash_table<T, U, chash>;
template<typename T> using pb_set = gp_hash_table<T, null_type, chash>;
#define K first
#define V second
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vii = vector<vector<int>>;
typedef vector<ll> vll;
using pll = pair<ll,ll>;
using pii = pair<int,int>;
constexpr ll NN = 5000,M = 10000;
vi nm(101);
int dp[NN][M];
int dp_p[NN][M];
int factors[M];
vi adj[NN];
int a[NN];
void dfs(int i,int p){
if(p != -1) adj[i].erase(ranges::find(adj[i],p));
for(int j : adj[i])
dfs(j,i);
for(int here=2;here<M;here++){
if(a[i]!=here) dp[i][here]=here;
int x = here;
vi primes;
while(x!=1){
primes.push_back(factors[x]), x/=factors[x];
}
for(int j : adj[i]){
int add = 10000;
for(int p : primes) add = min(dp_p[j][p],add);
dp[i][here]+=add;
}
for(int p : primes) dp_p[i][p] = min(dp_p[i][p],dp[i][here]);
}
}
void run()
{
int n; cin >> n;
int non_even = 0;
for(int i : rep(n)) cin >> a[i], non_even+=a[i]%2;
for(int u,v; int i : rep(n-1)){
cin >> u >> v,--u,--v;
adj[u].push_back(v),adj[v].push_back(u);
} dfs(0,-1);
int ans = non_even*2;
for(int i : rep(2,M)) ans = min(ans,dp[0][i]);
cout << ans << '\n';
}
int main()
{
//KING OF THE WORLD...... U.W.T.B
cin.tie(0);
ios_base::sync_with_stdio(false);
for(int i : rep(M)) for(auto &x : dp_p[i]) x=10000;
for(int i = 2;i<M;i++){
if(factors[i]==0) for(int j = i;j<NN;j+=i) factors[j]=i;
}
run();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
6 5 6 3 4 9 12 1 2 1 3 1 4 1 6 3 5