oj.uz

Submission #1082035

# Submission time Handle Problem Language Result Execution time Memory
1082035 2024-08-30T15:11:21 Z Tymond Cat Exercise (JOI23_ho_t4) C++17
31 / 100
 2000 ms 36236 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];
bool ok[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)];
}

int dfs2(int v, int k, int p){
    if(!ok[v]){
        return 0;
    }

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

void getBest(int v){
    for(auto u : g[v]){
        int res = dfs2(u, 0, v);
        if(res > 0){
            akt.pb(pos[res]);
        }
    }
}

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();
        ok[pos[i]] = 1;
        getBest(pos[i]);

       // cout << i << ' ' << pos[i] << '\n';
        for(auto ele : akt){
            //cout << ele << '\n';
            dp[pos[i]] = max(dp[pos[i]], (ll)dp[ele] + dist(pos[i], ele));
        }
    }

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

    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 24664 KB Output is correct
2 Correct 3 ms 24668 KB Output is correct
3 Correct 3 ms 24668 KB Output is correct
4 Correct 3 ms 24668 KB Output is correct
5 Correct 3 ms 24668 KB Output is correct
6 Correct 3 ms 24740 KB Output is correct
7 Correct 3 ms 24668 KB Output is correct
8 Correct 3 ms 24668 KB Output is correct
9 Correct 3 ms 24668 KB Output is correct
10 Correct 3 ms 24668 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 24664 KB Output is correct
2 Correct 3 ms 24668 KB Output is correct
3 Correct 3 ms 24668 KB Output is correct
4 Correct 3 ms 24668 KB Output is correct
5 Correct 3 ms 24668 KB Output is correct
6 Correct 3 ms 24740 KB Output is correct
7 Correct 3 ms 24668 KB Output is correct
8 Correct 3 ms 24668 KB Output is correct
9 Correct 3 ms 24668 KB Output is correct
10 Correct 3 ms 24668 KB Output is correct
11 Correct 3 ms 24668 KB Output is correct
12 Correct 3 ms 24668 KB Output is correct
13 Correct 3 ms 24668 KB Output is correct
14 Correct 3 ms 24668 KB Output is correct
15 Correct 3 ms 24668 KB Output is correct
16 Correct 3 ms 24668 KB Output is correct
17 Correct 3 ms 24668 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 24664 KB Output is correct
2 Correct 3 ms 24668 KB Output is correct
3 Correct 3 ms 24668 KB Output is correct
4 Correct 3 ms 24668 KB Output is correct
5 Correct 3 ms 24668 KB Output is correct
6 Correct 3 ms 24740 KB Output is correct
7 Correct 3 ms 24668 KB Output is correct
8 Correct 3 ms 24668 KB Output is correct
9 Correct 3 ms 24668 KB Output is correct
10 Correct 3 ms 24668 KB Output is correct
11 Correct 3 ms 24668 KB Output is correct
12 Correct 3 ms 24668 KB Output is correct
13 Correct 3 ms 24668 KB Output is correct
14 Correct 3 ms 24668 KB Output is correct
15 Correct 3 ms 24668 KB Output is correct
16 Correct 3 ms 24668 KB Output is correct
17 Correct 3 ms 24668 KB Output is correct
18 Correct 87 ms 25208 KB Output is correct
19 Correct 76 ms 25172 KB Output is correct
20 Correct 77 ms 25168 KB Output is correct
21 Correct 5 ms 25180 KB Output is correct
22 Correct 5 ms 24924 KB Output is correct
23 Correct 6 ms 24920 KB Output is correct
24 Correct 5 ms 24924 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 24664 KB Output is correct
2 Correct 3 ms 24668 KB Output is correct
3 Correct 3 ms 24668 KB Output is correct
4 Correct 3 ms 24668 KB Output is correct
5 Correct 3 ms 24668 KB Output is correct
6 Correct 3 ms 24740 KB Output is correct
7 Correct 3 ms 24668 KB Output is correct
8 Correct 3 ms 24668 KB Output is correct
9 Correct 3 ms 24668 KB Output is correct
10 Correct 3 ms 24668 KB Output is correct
11 Correct 3 ms 24668 KB Output is correct
12 Correct 3 ms 24668 KB Output is correct
13 Correct 3 ms 24668 KB Output is correct
14 Correct 3 ms 24668 KB Output is correct
15 Correct 3 ms 24668 KB Output is correct
16 Correct 3 ms 24668 KB Output is correct
17 Correct 3 ms 24668 KB Output is correct
18 Correct 87 ms 25208 KB Output is correct
19 Correct 76 ms 25172 KB Output is correct
20 Correct 77 ms 25168 KB Output is correct
21 Correct 5 ms 25180 KB Output is correct
22 Correct 5 ms 24924 KB Output is correct
23 Correct 6 ms 24920 KB Output is correct
24 Correct 5 ms 24924 KB Output is correct
25 Correct 3 ms 24668 KB Output is correct
26 Correct 78 ms 25076 KB Output is correct
27 Correct 80 ms 24920 KB Output is correct
28 Correct 81 ms 25088 KB Output is correct
29 Correct 79 ms 25076 KB Output is correct
30 Correct 8 ms 24664 KB Output is correct
31 Correct 10 ms 24924 KB Output is correct
32 Correct 9 ms 24868 KB Output is correct
33 Correct 10 ms 24924 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 24664 KB Output is correct
2 Correct 3 ms 24668 KB Output is correct
3 Correct 3 ms 24668 KB Output is correct
4 Correct 3 ms 24668 KB Output is correct
5 Correct 3 ms 24668 KB Output is correct
6 Correct 3 ms 24740 KB Output is correct
7 Correct 3 ms 24668 KB Output is correct
8 Correct 3 ms 24668 KB Output is correct
9 Correct 3 ms 24668 KB Output is correct
10 Correct 3 ms 24668 KB Output is correct
11 Correct 3 ms 24668 KB Output is correct
12 Correct 3 ms 24668 KB Output is correct
13 Correct 3 ms 24668 KB Output is correct
14 Correct 3 ms 24668 KB Output is correct
15 Correct 3 ms 24668 KB Output is correct
16 Correct 3 ms 24668 KB Output is correct
17 Correct 3 ms 24668 KB Output is correct
18 Correct 87 ms 25208 KB Output is correct
19 Correct 76 ms 25172 KB Output is correct
20 Correct 77 ms 25168 KB Output is correct
21 Correct 5 ms 25180 KB Output is correct
22 Correct 5 ms 24924 KB Output is correct
23 Correct 6 ms 24920 KB Output is correct
24 Correct 5 ms 24924 KB Output is correct
25 Execution timed out 2065 ms 36236 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 24664 KB Output is correct
2 Correct 4 ms 24920 KB Output is correct
3 Execution timed out 2077 ms 31060 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 24664 KB Output is correct
2 Correct 3 ms 24668 KB Output is correct
3 Correct 3 ms 24668 KB Output is correct
4 Correct 3 ms 24668 KB Output is correct
5 Correct 3 ms 24668 KB Output is correct
6 Correct 3 ms 24740 KB Output is correct
7 Correct 3 ms 24668 KB Output is correct
8 Correct 3 ms 24668 KB Output is correct
9 Correct 3 ms 24668 KB Output is correct
10 Correct 3 ms 24668 KB Output is correct
11 Correct 3 ms 24668 KB Output is correct
12 Correct 3 ms 24668 KB Output is correct
13 Correct 3 ms 24668 KB Output is correct
14 Correct 3 ms 24668 KB Output is correct
15 Correct 3 ms 24668 KB Output is correct
16 Correct 3 ms 24668 KB Output is correct
17 Correct 3 ms 24668 KB Output is correct
18 Correct 87 ms 25208 KB Output is correct
19 Correct 76 ms 25172 KB Output is correct
20 Correct 77 ms 25168 KB Output is correct
21 Correct 5 ms 25180 KB Output is correct
22 Correct 5 ms 24924 KB Output is correct
23 Correct 6 ms 24920 KB Output is correct
24 Correct 5 ms 24924 KB Output is correct
25 Correct 3 ms 24668 KB Output is correct
26 Correct 78 ms 25076 KB Output is correct
27 Correct 80 ms 24920 KB Output is correct
28 Correct 81 ms 25088 KB Output is correct
29 Correct 79 ms 25076 KB Output is correct
30 Correct 8 ms 24664 KB Output is correct
31 Correct 10 ms 24924 KB Output is correct
32 Correct 9 ms 24868 KB Output is correct
33 Correct 10 ms 24924 KB Output is correct
34 Execution timed out 2065 ms 36236 KB Time limit exceeded
35 Halted 0 ms 0 KB -