oj.uz

Submission #1040225

# Submission time Handle Problem Language Result Execution time Memory
1040225 2024-07-31T19:01:22 Z TAhmed33 Cat Exercise (JOI23_ho_t4) C++
21 / 100
 2000 ms 48328 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 25;
const int B = 19;
typedef long long ll;
int a[MAXN], n;
vector <int> adj[MAXN];
struct DSU {
    int par[MAXN];
    pair <int, int> mx[MAXN];
    void init () {
        for (int i = 1; i <= n; i++) {
            par[i] = i; mx[i] = {a[i], i};
        }
    }
    int find (int x) {
        return par[x] == x ? x : par[x] = find(par[x]);
    }
    void merge (int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return;
        par[x] = y; if (mx[x].first > mx[y].first) {
            mx[y] = mx[x];
        }
    }
} cur;
vector <int> adj2[MAXN];
int dp[B][MAXN], dep[MAXN];
int jump (int x, int y) {
    for (int i = B - 1; i >= 0; i--) {
        if (y & (1 << i)) {
            x = dp[i][x];
        }
    }
    return x;
}
int lca (int x, int y) {
    if (dep[x] > dep[y]) swap(x, y);
    y = jump(y, dep[y] - dep[x]);
    if (x == y) return x ;
    for (int i = B - 1; i >= 0; i--) {
        if (dp[i][x] != dp[i][y]) {
            x = dp[i][x], y = dp[i][x];
        }
    }
    return dp[0][x];
}
int dist (int x, int y) {
    return dep[x] + dep[y] - 2 * dep[lca(x, y)];
}
ll dfs (int pos) {
    if (adj2[pos].empty()) return 0;
    ll mx = 0;
    for (auto j : adj2[pos]) {
        mx = max(mx, dist(j, pos) + dfs(j));
    }
    return mx;
}
void dfs2 (int pos, int par) {
    for (auto j : adj[pos]) {
        if (j != par) {
            dp[0][j] = pos;
            for (int i = 1; i < B; i++) {
                dp[i][j] = dp[i - 1][dp[i - 1][j]];
            }
            dep[j] = 1 + dep[pos];
            dfs2(j, pos);
        }
    }
}
vector <int> yy;
void dfs3 (int pos, int par, int mx) {
    mx = max(mx, a[pos]);
    if (mx == a[pos] && par != -1) {
        yy.push_back(pos);
    }
    for (auto j : adj[pos]) {
        if (j != par) {
            dfs3(j, pos, mx);
        }
    }
}
void solve () {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i < n; i++) {
        int x, y; cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    dfs2(1, 0);
    vector <int> ii;
    for (int i = 1; i <= n; i++) {
        ii.push_back(i);
    }
    sort(ii.begin(), ii.end(), [&] (int x, int y) {
        return a[x] < a[y];
    });
    cur.init();
/*    for (auto i : ii) {
        for (auto j : adj[i]) {
            if (a[j] > a[i]) {
                continue;
            }
            auto g = cur.mx[cur.find(j)].second;
            adj2[i].push_back(g);
            cur.merge(g, i);
        }
    }*/
    int root = -1;
    for (int i = 1; i <= n; i++) {
        if (a[i] == n) {
            root = i;
        }
    }
    for (int i = 1; i <= n; i++) {
        yy.clear();
        dfs3(i, -1, 0);
        sort(yy.begin(), yy.end(), [&] (int x, int y) {
            return a[x] < a[y];
        });
        if (!yy.empty()) {
            adj2[yy.front()].push_back(i);
        }
    }
    cout << dfs(root) << '\n';
}       
signed main () {
    ios::sync_with_stdio(0); cin.tie(0);
    int tc = 1; //cin >> tc;
    while (tc--) solve();
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 27484 KB Output is correct
2 Correct 3 ms 27484 KB Output is correct
3 Correct 3 ms 27484 KB Output is correct
4 Correct 3 ms 27484 KB Output is correct
5 Correct 3 ms 27484 KB Output is correct
6 Correct 3 ms 27564 KB Output is correct
7 Correct 3 ms 27680 KB Output is correct
8 Correct 3 ms 27484 KB Output is correct
9 Correct 3 ms 27484 KB Output is correct
10 Correct 3 ms 27484 KB Output is correct

Subtask #2
7.0 / 7.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 27484 KB Output is correct
2 Correct 3 ms 27484 KB Output is correct
3 Correct 3 ms 27484 KB Output is correct
4 Correct 3 ms 27484 KB Output is correct
5 Correct 3 ms 27484 KB Output is correct
6 Correct 3 ms 27564 KB Output is correct
7 Correct 3 ms 27680 KB Output is correct
8 Correct 3 ms 27484 KB Output is correct
9 Correct 3 ms 27484 KB Output is correct
10 Correct 3 ms 27484 KB Output is correct
11 Correct 6 ms 27484 KB Output is correct
12 Correct 4 ms 27484 KB Output is correct
13 Correct 4 ms 27484 KB Output is correct
14 Correct 4 ms 27484 KB Output is correct
15 Correct 3 ms 27484 KB Output is correct
16 Correct 3 ms 27484 KB Output is correct
17 Correct 3 ms 27484 KB Output is correct
18 Correct 511 ms 28256 KB Output is correct
19 Correct 424 ms 28248 KB Output is correct
20 Correct 466 ms 28248 KB Output is correct
21 Correct 132 ms 28232 KB Output is correct
22 Correct 143 ms 28228 KB Output is correct
23 Correct 136 ms 28244 KB Output is correct
24 Correct 129 ms 28240 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 27484 KB Output is correct
2 Correct 3 ms 27484 KB Output is correct
3 Correct 3 ms 27484 KB Output is correct
4 Correct 3 ms 27484 KB Output is correct
5 Correct 3 ms 27484 KB Output is correct
6 Correct 3 ms 27564 KB Output is correct
7 Correct 3 ms 27680 KB Output is correct
8 Correct 3 ms 27484 KB Output is correct
9 Correct 3 ms 27484 KB Output is correct
10 Correct 3 ms 27484 KB Output is correct
11 Correct 6 ms 27484 KB Output is correct
12 Correct 4 ms 27484 KB Output is correct
13 Correct 4 ms 27484 KB Output is correct
14 Correct 4 ms 27484 KB Output is correct
15 Correct 3 ms 27484 KB Output is correct
16 Correct 3 ms 27484 KB Output is correct
17 Correct 3 ms 27484 KB Output is correct
18 Correct 511 ms 28256 KB Output is correct
19 Correct 424 ms 28248 KB Output is correct
20 Correct 466 ms 28248 KB Output is correct
21 Correct 132 ms 28232 KB Output is correct
22 Correct 143 ms 28228 KB Output is correct
23 Correct 136 ms 28244 KB Output is correct
24 Correct 129 ms 28240 KB Output is correct
25 Correct 3 ms 27480 KB Output is correct
26 Correct 424 ms 28180 KB Output is correct
27 Incorrect 447 ms 28244 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 27484 KB Output is correct
2 Correct 3 ms 27484 KB Output is correct
3 Correct 3 ms 27484 KB Output is correct
4 Correct 3 ms 27484 KB Output is correct
5 Correct 3 ms 27484 KB Output is correct
6 Correct 3 ms 27564 KB Output is correct
7 Correct 3 ms 27680 KB Output is correct
8 Correct 3 ms 27484 KB Output is correct
9 Correct 3 ms 27484 KB Output is correct
10 Correct 3 ms 27484 KB Output is correct
11 Correct 6 ms 27484 KB Output is correct
12 Correct 4 ms 27484 KB Output is correct
13 Correct 4 ms 27484 KB Output is correct
14 Correct 4 ms 27484 KB Output is correct
15 Correct 3 ms 27484 KB Output is correct
16 Correct 3 ms 27484 KB Output is correct
17 Correct 3 ms 27484 KB Output is correct
18 Correct 511 ms 28256 KB Output is correct
19 Correct 424 ms 28248 KB Output is correct
20 Correct 466 ms 28248 KB Output is correct
21 Correct 132 ms 28232 KB Output is correct
22 Correct 143 ms 28228 KB Output is correct
23 Correct 136 ms 28244 KB Output is correct
24 Correct 129 ms 28240 KB Output is correct
25 Execution timed out 2040 ms 48328 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 27480 KB Output is correct
2 Incorrect 3 ms 27484 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 27484 KB Output is correct
2 Correct 3 ms 27484 KB Output is correct
3 Correct 3 ms 27484 KB Output is correct
4 Correct 3 ms 27484 KB Output is correct
5 Correct 3 ms 27484 KB Output is correct
6 Correct 3 ms 27564 KB Output is correct
7 Correct 3 ms 27680 KB Output is correct
8 Correct 3 ms 27484 KB Output is correct
9 Correct 3 ms 27484 KB Output is correct
10 Correct 3 ms 27484 KB Output is correct
11 Correct 6 ms 27484 KB Output is correct
12 Correct 4 ms 27484 KB Output is correct
13 Correct 4 ms 27484 KB Output is correct
14 Correct 4 ms 27484 KB Output is correct
15 Correct 3 ms 27484 KB Output is correct
16 Correct 3 ms 27484 KB Output is correct
17 Correct 3 ms 27484 KB Output is correct
18 Correct 511 ms 28256 KB Output is correct
19 Correct 424 ms 28248 KB Output is correct
20 Correct 466 ms 28248 KB Output is correct
21 Correct 132 ms 28232 KB Output is correct
22 Correct 143 ms 28228 KB Output is correct
23 Correct 136 ms 28244 KB Output is correct
24 Correct 129 ms 28240 KB Output is correct
25 Correct 3 ms 27480 KB Output is correct
26 Correct 424 ms 28180 KB Output is correct
27 Incorrect 447 ms 28244 KB Output isn't correct
28 Halted 0 ms 0 KB -