QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #483818 | #4584. Not One | Thirvin# | WA | 51ms | 9864kb | C++20 | 4.2kb | 2024-07-19 13:31:26 | 2024-07-19 13:31:27 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define sz(x) signed(size(x))
#define fi first
#define se second
inline void solve() {
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; ++i)
cin >> a[i];
vector<vector<int>> edges(n + 1);
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
edges[u].emplace_back(v);
edges[v].emplace_back(u);
}
{
int tmp = a[1];
for (int i = 2; i <= n; ++i) {
tmp = gcd(tmp, a[i]);
if (tmp == 1)
break;
}
if (tmp != 1) {
cout << n;
return;
}
}
vector<int> sub(n + 1), si(n + 1);
auto dfs1 = [&](auto&& self, int cur, int par) -> void {
sub[cur] = a[cur];
si[cur] = 1;
for (int nxt : edges[cur]) {
if(nxt == par) continue;
self(self, nxt, cur);
sub[cur] = gcd(sub[cur], sub[nxt]);
si[cur] += si[nxt];
}
return;
};
dfs1(dfs1, 1, 0);
int ans = 0;
auto dfs2 = [&](auto&& self, int cur, int par, int pre) -> void {
vector<pair<int, int>> v;
if (par != 0)
v.emplace_back(pre, n - si[cur]);
for (int nxt : edges[cur]) {
if (nxt == par) continue;
v.emplace_back(sub[nxt], si[nxt]);
}
vector<int> gg(sz(v)), ggg(sz(v) + 1);
ggg.back() = a[cur];
gg[0] = gcd(a[cur], v[0].fi);
for (int i = 1; i < sz(v); ++i)
gg[i] = gcd(gg[i - 1], v[i].fi);
for (int i = sz(v) - 1; i >= 0; --i)
ggg[i] = gcd(ggg[i + 1], v[i].fi);
if (sz(v) == 1)
ans = max(ans, (a[cur] != 1 ? 1 : 0));
else {
for (int i = 0; i < sz(v); ++i) {
if (i == 0) {
if (ggg[1] == 1) continue;
ans = max(ans, n - v[i].se);
}
else if (i == sz(v) - 1) {
if (gg[i - 1] == 1) continue;
ans = max(ans, n - v[i].se);
}
else {
if (gcd(gg[i - 1], ggg[i + 1]) == 1) continue;
ans = max(ans, n - v[i].se);
}
}
}
if (par == 0) {
for (int i = 0; i < sz(edges[cur]); ++i) {
int tmp;
if (i == 0)
tmp = ggg[i + 1];
else if (i == sz(edges[cur]) - 1)
tmp = gg[i - 1];
else
tmp = gcd(gg[i - 1], ggg[i + 1]);
self(self, edges[cur][i], cur, tmp);
}
}
else {
int tt = gcd(pre, a[cur]);
for (int nxt : edges[cur]) {
if (nxt == par) continue;
self(self, nxt, cur, tt);
}
}
};
dfs2(dfs2, 1, 0, 0);
cout << ans << '\n';
return;
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
int t = 1;
while (t--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3624kb
input:
7 10 5 8 6 10 6 4 1 2 2 3 2 4 4 5 4 6 4 7
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
4 1 1 1 1 1 2 2 3 3 4
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
5 100 100 100 100 100 3 4 1 2 3 5 2 4
output:
5
result:
ok single line: '5'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
2 1 1 1 2
output:
0
result:
ok single line: '0'
Test #5:
score: -100
Wrong Answer
time: 51ms
memory: 9864kb
input:
100000 860163 795323 862289 543383 792647 337047 353985 959953 874318 573652 69827 958063 571741 704399 311826 920477 792478 151531 872269 592307 853819 865817 940735 620657 937154 696551 749279 552523 836161 707467 389626 459089 563763 668884 810391 639709 419361 580342 519595 836124 494959 669379 ...
output:
6
result:
wrong answer 1st lines differ - expected: '213', found: '6'