oj.uz

Submission #1082028

# Submission time Handle Problem Language Result Execution time Memory
1082028 2024-08-30T14:55:58 Z Tymond Cat Exercise (JOI23_ho_t4) C++17
31 / 100
 2000 ms 42680 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define fi first
#define se second
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        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);
    }
};

const int MAXN = 2e5 + 7;
const int MAXK = 20;
vi g[MAXN];
int a[MAXN];
ll dp[MAXN];
int pos[MAXN];
int dep[MAXN];
int jump[MAXK][MAXN];
int n;
vi akt;

void dfs(int v, int p, int d){
    dep[v] = d;
    jump[0][v] = p;
    for(auto u : g[v]){
        if(u != p){
            dfs(u, v, d + 1);
        }
    }
}

void preprocessing(){
    dfs(1, 1, 0);
    for(int i = 1; i < MAXK; i++){
        for(int j = 1; j <= n; j++){
            jump[i][j] = jump[i - 1][jump[i - 1][j]];
        }
    }
}

int lca(int u, int v){
    if(dep[u] > dep[v]){
        swap(u, v);
    }

    for(int i = MAXK - 1; i >= 0; i--){
        if(dep[v] - dep[u] >= (1 << i)){
            v = jump[i][v];
        }
    }

    if(u == v){
        return v;
    }

    for(int i = MAXK - 1; i >= 0; i--){
        if(jump[i][u] != jump[i][v]){
            u = jump[i][u];
            v = jump[i][v];
        }
    }

    return jump[0][v];
}

int dist(int u, int v){
    return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}

void dfs2(int v, int k, int pk, int p){
    if(a[v] > k && a[v] < pk){
        akt.pb(v);
    }

    for(auto u : g[v]){
        if(u != p){
            dfs2(u, (p == 0 ? k : max(k, a[v])), pk, v);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        pos[a[i]] = i;
    }

    for(int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }

    preprocessing();
    for(int i = 1; i <= n; i++){
        akt.clear();
        dfs2(pos[i], 0, i, 0);
       // cout << i << ' ' << pos[i] << '\n';
        for(auto ele : akt){
         //   cout << ele << ' ' << (ll)dp[ele] + dist(pos[i], ele) << '\n';
            dp[pos[i]] = max(dp[pos[i]], (ll)dp[ele] + dist(pos[i], ele));
        }

       // cout<< dp[pos[i]] << '\n';
    }

    cout << dp[pos[n]] << '\n';

    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 22364 KB Output is correct
2 Correct 4 ms 22324 KB Output is correct
3 Correct 3 ms 22364 KB Output is correct
4 Correct 4 ms 22464 KB Output is correct
5 Correct 3 ms 22364 KB Output is correct
6 Correct 4 ms 22364 KB Output is correct
7 Correct 3 ms 22364 KB Output is correct
8 Correct 3 ms 22504 KB Output is correct
9 Correct 4 ms 22364 KB Output is correct
10 Correct 4 ms 22364 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 22364 KB Output is correct
2 Correct 4 ms 22324 KB Output is correct
3 Correct 3 ms 22364 KB Output is correct
4 Correct 4 ms 22464 KB Output is correct
5 Correct 3 ms 22364 KB Output is correct
6 Correct 4 ms 22364 KB Output is correct
7 Correct 3 ms 22364 KB Output is correct
8 Correct 3 ms 22504 KB Output is correct
9 Correct 4 ms 22364 KB Output is correct
10 Correct 4 ms 22364 KB Output is correct
11 Correct 5 ms 22364 KB Output is correct
12 Correct 3 ms 22496 KB Output is correct
13 Correct 4 ms 22364 KB Output is correct
14 Correct 5 ms 22468 KB Output is correct
15 Correct 5 ms 22364 KB Output is correct
16 Correct 4 ms 22360 KB Output is correct
17 Correct 4 ms 22364 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 22364 KB Output is correct
2 Correct 4 ms 22324 KB Output is correct
3 Correct 3 ms 22364 KB Output is correct
4 Correct 4 ms 22464 KB Output is correct
5 Correct 3 ms 22364 KB Output is correct
6 Correct 4 ms 22364 KB Output is correct
7 Correct 3 ms 22364 KB Output is correct
8 Correct 3 ms 22504 KB Output is correct
9 Correct 4 ms 22364 KB Output is correct
10 Correct 4 ms 22364 KB Output is correct
11 Correct 5 ms 22364 KB Output is correct
12 Correct 3 ms 22496 KB Output is correct
13 Correct 4 ms 22364 KB Output is correct
14 Correct 5 ms 22468 KB Output is correct
15 Correct 5 ms 22364 KB Output is correct
16 Correct 4 ms 22360 KB Output is correct
17 Correct 4 ms 22364 KB Output is correct
18 Correct 205 ms 22956 KB Output is correct
19 Correct 173 ms 23140 KB Output is correct
20 Correct 189 ms 23132 KB Output is correct
21 Correct 201 ms 23164 KB Output is correct
22 Correct 189 ms 23128 KB Output is correct
23 Correct 189 ms 23136 KB Output is correct
24 Correct 212 ms 23160 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 22364 KB Output is correct
2 Correct 4 ms 22324 KB Output is correct
3 Correct 3 ms 22364 KB Output is correct
4 Correct 4 ms 22464 KB Output is correct
5 Correct 3 ms 22364 KB Output is correct
6 Correct 4 ms 22364 KB Output is correct
7 Correct 3 ms 22364 KB Output is correct
8 Correct 3 ms 22504 KB Output is correct
9 Correct 4 ms 22364 KB Output is correct
10 Correct 4 ms 22364 KB Output is correct
11 Correct 5 ms 22364 KB Output is correct
12 Correct 3 ms 22496 KB Output is correct
13 Correct 4 ms 22364 KB Output is correct
14 Correct 5 ms 22468 KB Output is correct
15 Correct 5 ms 22364 KB Output is correct
16 Correct 4 ms 22360 KB Output is correct
17 Correct 4 ms 22364 KB Output is correct
18 Correct 205 ms 22956 KB Output is correct
19 Correct 173 ms 23140 KB Output is correct
20 Correct 189 ms 23132 KB Output is correct
21 Correct 201 ms 23164 KB Output is correct
22 Correct 189 ms 23128 KB Output is correct
23 Correct 189 ms 23136 KB Output is correct
24 Correct 212 ms 23160 KB Output is correct
25 Correct 4 ms 22364 KB Output is correct
26 Correct 245 ms 23092 KB Output is correct
27 Correct 265 ms 23096 KB Output is correct
28 Correct 271 ms 23252 KB Output is correct
29 Correct 263 ms 23100 KB Output is correct
30 Correct 217 ms 22788 KB Output is correct
31 Correct 202 ms 22620 KB Output is correct
32 Correct 186 ms 22620 KB Output is correct
33 Correct 189 ms 22784 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 22364 KB Output is correct
2 Correct 4 ms 22324 KB Output is correct
3 Correct 3 ms 22364 KB Output is correct
4 Correct 4 ms 22464 KB Output is correct
5 Correct 3 ms 22364 KB Output is correct
6 Correct 4 ms 22364 KB Output is correct
7 Correct 3 ms 22364 KB Output is correct
8 Correct 3 ms 22504 KB Output is correct
9 Correct 4 ms 22364 KB Output is correct
10 Correct 4 ms 22364 KB Output is correct
11 Correct 5 ms 22364 KB Output is correct
12 Correct 3 ms 22496 KB Output is correct
13 Correct 4 ms 22364 KB Output is correct
14 Correct 5 ms 22468 KB Output is correct
15 Correct 5 ms 22364 KB Output is correct
16 Correct 4 ms 22360 KB Output is correct
17 Correct 4 ms 22364 KB Output is correct
18 Correct 205 ms 22956 KB Output is correct
19 Correct 173 ms 23140 KB Output is correct
20 Correct 189 ms 23132 KB Output is correct
21 Correct 201 ms 23164 KB Output is correct
22 Correct 189 ms 23128 KB Output is correct
23 Correct 189 ms 23136 KB Output is correct
24 Correct 212 ms 23160 KB Output is correct
25 Execution timed out 2086 ms 42680 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 22360 KB Output is correct
2 Correct 4 ms 22468 KB Output is correct
3 Execution timed out 2087 ms 34612 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 22364 KB Output is correct
2 Correct 4 ms 22324 KB Output is correct
3 Correct 3 ms 22364 KB Output is correct
4 Correct 4 ms 22464 KB Output is correct
5 Correct 3 ms 22364 KB Output is correct
6 Correct 4 ms 22364 KB Output is correct
7 Correct 3 ms 22364 KB Output is correct
8 Correct 3 ms 22504 KB Output is correct
9 Correct 4 ms 22364 KB Output is correct
10 Correct 4 ms 22364 KB Output is correct
11 Correct 5 ms 22364 KB Output is correct
12 Correct 3 ms 22496 KB Output is correct
13 Correct 4 ms 22364 KB Output is correct
14 Correct 5 ms 22468 KB Output is correct
15 Correct 5 ms 22364 KB Output is correct
16 Correct 4 ms 22360 KB Output is correct
17 Correct 4 ms 22364 KB Output is correct
18 Correct 205 ms 22956 KB Output is correct
19 Correct 173 ms 23140 KB Output is correct
20 Correct 189 ms 23132 KB Output is correct
21 Correct 201 ms 23164 KB Output is correct
22 Correct 189 ms 23128 KB Output is correct
23 Correct 189 ms 23136 KB Output is correct
24 Correct 212 ms 23160 KB Output is correct
25 Correct 4 ms 22364 KB Output is correct
26 Correct 245 ms 23092 KB Output is correct
27 Correct 265 ms 23096 KB Output is correct
28 Correct 271 ms 23252 KB Output is correct
29 Correct 263 ms 23100 KB Output is correct
30 Correct 217 ms 22788 KB Output is correct
31 Correct 202 ms 22620 KB Output is correct
32 Correct 186 ms 22620 KB Output is correct
33 Correct 189 ms 22784 KB Output is correct
34 Execution timed out 2086 ms 42680 KB Time limit exceeded
35 Halted 0 ms 0 KB -