QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#321634	#4584. Not One	ssuyu	TL	0ms	29696kb	C++17	2.1kb	2024-02-05 02:09:32	2024-02-05 02:09:32

Judging History

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

[2024-02-05 02:09:32]
评测

测评结果：TL
用时：0ms
内存：29696kb

查看

[2024-02-05 02:09:32]
提交

answer

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define ssuyu                                                                  \
    ios_base::sync_with_stdio(0);                                              \
    cin.tie(0)
#define pb push_back
#define F first
#define S second
#define pii pair<int, int>
#define int long long
#define PI acos(-1)
#define all(x) (x).begin(), (x).end()
const int N = 1e6 + 5;
int a[N];
int prime[N] = {0}, f[N] = {0};
vector<int> primes;
int Find(int a) {
    if (f[a] <= 0) {
        return a;
    } else
        return f[a] = Find(f[a]);
}
int Union(int a, int b) {
    int fa = Find(a);
    int fb = Find(b);
    if (fa == fb)
        return -f[fa];
    if (f[fa] > f[fb])
        swap(fa, fb);
    f[fa] += f[fb];
    f[fb] = fa;
    return -f[fa];
}
void getprimes(int n) {
    for (int i = 2; i <= n; i++) {
        if (!prime[i]) {
            primes.pb(i);
        }
        for (auto u : primes) {
            if (u * i > n)
                break;
            prime[u * i] = 1;
            if (!(i % u))
                break;
        }
    }
}
struct edge {
    int u;
    int v;
    int w = 1;
} edge[N];
signed main() {
    int n, m, x, y;
    int mx = 0, ans = 0;
    vector<int> affect;
    map<int, vector<pii>> mp;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        mx = max(mx, a[i]);
    }
    getprimes(mx);
    for (int i = 0; i < n - 1; i++) {
        cin >> x >> y;
        f[x] = f[y] = -1;
        int w = __gcd(a[x], a[y]);
        for (int j = 0; j < primes.size() && primes[j] <= w; j++) {
            if (w % primes[j] == 0) {
                mp[primes[j]].pb({x, y});
            }
            while (w % primes[j] == 0)
                w /= primes[j];
        }
    }
    for (auto p : mp) {
        for (auto u : p.S) {
            ans = max(Union(u.F, u.S), ans);
            affect.pb(u.F);
            affect.pb(u.S);
        }
        for (auto u : affect)
            f[u] = -1;
        affect.clear();
    }
    cout << ans;
}

源文件, 语言: C++17

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 29104kb

input:

7
10 5 8 6 10 6 4
1 2
2 3
2 4
4 5
4 6
4 7

output:

result:

ok single line: '4'

Test #2:

score: 0

Accepted

time: 0ms

memory: 29508kb

input:

output:

result:

ok single line: '0'

Test #3:

score: 0

Accepted

time: 0ms

memory: 29536kb

input:

5
100 100 100 100 100
3 4
1 2
3 5
2 4

output:

result:

ok single line: '5'

Test #4:

score: 0

Accepted

time: 0ms

memory: 29696kb

input:

2
1 1
1 2

output:

result:

ok single line: '0'

Test #5:

score: -100

Time Limit Exceeded

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 ...