QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#626300#4229. GCD Harmonynickbelov#TL 5ms5708kbC++202.7kb2024-10-10 02:41:512024-10-10 02:41:51

Judging History

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

  • [2024-10-10 02:41:51]
  • 评测
  • 测评结果:TL
  • 用时:5ms
  • 内存:5708kb
  • [2024-10-10 02:41:51]
  • 提交

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 = 250; 

int dp[NN][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;
        for(int j : adj[i]){
            auto &v = dp[j];
            int add = v[here];

            for(int c=2;c<M;c++) 
                if((((c&1)==0) and ((here&1)==0)) or (c%3==0 and here%3==0) or (gcd(c,here)>1))
                    add=min(add,v[c]);
            
            dp[i][here]+=add;
        }
    }

}

void run()
{
    int n; cin >> n;
    for(int i : rep(n)) cin >> a[i];   
    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 = dp[0][2];
    for(int c : rep(2,M)) ans = min(ans,dp[0][c]);

    cout << ans << '\n';
}

int main()
{
    //KING OF THE WORLD...... U.W.T.B
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    run();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 3640kb

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: 3ms
memory: 3660kb

input:

3
1
2
3
3 1
2 3

output:

4

result:

ok single line: '4'

Test #3:

score: 0
Accepted
time: 5ms
memory: 3584kb

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:

15

result:

ok single line: '15'

Test #4:

score: 0
Accepted
time: 4ms
memory: 3644kb

input:

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

output:

14

result:

ok single line: '14'

Test #5:

score: 0
Accepted
time: 4ms
memory: 5708kb

input:

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

output:

13

result:

ok single line: '13'

Test #6:

score: -100
Time Limit Exceeded

input:

5000
59
25
51
26
33
99
2
13
29
58
5
47
96
83
63
22
69
89
41
90
20
97
85
90
55
17
54
75
54
24
90
54
74
78
81
77
2
47
68
18
60
81
99
86
7
6
76
43
17
43
92
25
36
26
47
100
63
66
2
16
47
25
48
86
24
2
10
42
44
80
92
48
49
21
49
40
32
85
53
88
15
30
4
27
77
16
6
80
50
56
46
14
3
48
92
50
93
35
69
29
48
4...

output:


result: