Submission #945438

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
945438	2024-03-13T19:25:16 Z	vladilius	Cat Exercise (JOI23_ho_t4)	C++17	54 / 100	199 ms	61328 KB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

struct dsu{
    vector<int> sz, p, m, a;
    int n;
    dsu(int ns, vector<int>& as){
        a = as;
        n = ns;
        p.resize(n + 1);
        sz.resize(n + 1);
        m.resize(n + 1);
        for (int i = 1; i <= n; i++){
            p[i] = m[i] = i;
            sz[i] = 1;
        }
    }
    int get(int v){
        if (p[v] != v){
            p[v] = get(p[v]);
        }
        return p[v];
    }
    void unite(int x, int y){
        x = get(x); y = get(y);
        if (x == y) return;
        if (sz[x] > sz[y]){
            swap(x, y);
        }
        p[x] = y;
        sz[y] += sz[x];
        if (a[m[x]] > a[m[y]]){
            m[y] = m[x];
        }
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n; cin>>n;
    vector<int> a(n + 1), p(n + 1);
    int s = 0;
    for (int i = 1; i <= n; i++){
        cin>>a[i];
        if (a[i] == n){
            s = i;
        }
        p[a[i]] = i;
    }
    vector<int> g[n + 1];
    for (int i = 1; i < n; i++){
        int u, v; cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dsu T(n + 1, a);
    
    vector<int> tin(n + 1), tout(n + 1), pw[n + 1], d(n + 1);
    int lg = ceil(log2(n)), timer = 0;
    for (int i = 1; i <= n; i++){
        pw[i].resize(lg);
    }
    function<void(int, int)> fill = [&](int v, int pr){
        tin[v] = timer++;
        pw[v][0] = pr;
        for (int i = 1; i < lg; i++){
            pw[v][i] = pw[pw[v][i - 1]][i - 1];
        }
        for (int i: g[v]){
            if (i == pr) continue;
            d[i] = d[v] + 1;
            fill(i, v);
        }
        tout[v] = timer++;
    };
    fill(1, 1);
    auto check = [&](int x, int y){
        return (tin[x] <= tin[y] && tout[x] >= tout[y]);
    };
    auto lca = [&](int x, int y){
        if (check(x, y)) return x;
        if (check(y, x)) return y;
        for (int i = lg - 1; i >= 0; i--){
            if (!check(pw[x][i], y)){
                x = pw[x][i];
            }
        }
        return pw[x][0];
    };
    auto dist = [&](int x, int y){
        return d[x] + d[y] - 2 * d[lca(x, y)];
    };
    vector<int> f(n + 1);
    for (int k = 1; k < n; k++){
        int i = p[k];
        for (int j: g[i]){
            if (a[j] > a[i]) continue;
            int v = T.m[T.get(j)];
            f[i] = max(f[i], f[v] + dist(i, v));
            T.unite(i, j);
        }
    }
    int out = 0;
    for (int i = 1; i <= n; i++){
        out = max(out, f[i] + dist(i, s));
    }
    cout<<out<<"\n";
}

Subtask #1
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct

Subtask #2
7.0 / 7.0

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

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	1 ms	600 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	344 KB	Output is correct
18	Correct	4 ms	1852 KB	Output is correct
19	Correct	3 ms	1880 KB	Output is correct
20	Correct	3 ms	1884 KB	Output is correct
21	Correct	3 ms	1748 KB	Output is correct
22	Correct	3 ms	1884 KB	Output is correct
23	Correct	3 ms	2136 KB	Output is correct
24	Correct	4 ms	1832 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	1 ms	600 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	344 KB	Output is correct
18	Correct	4 ms	1852 KB	Output is correct
19	Correct	3 ms	1880 KB	Output is correct
20	Correct	3 ms	1884 KB	Output is correct
21	Correct	3 ms	1748 KB	Output is correct
22	Correct	3 ms	1884 KB	Output is correct
23	Correct	3 ms	2136 KB	Output is correct
24	Correct	4 ms	1832 KB	Output is correct
25	Correct	0 ms	348 KB	Output is correct
26	Correct	3 ms	1628 KB	Output is correct
27	Correct	3 ms	1628 KB	Output is correct
28	Correct	4 ms	1488 KB	Output is correct
29	Correct	3 ms	1628 KB	Output is correct
30	Correct	3 ms	1372 KB	Output is correct
31	Correct	3 ms	1372 KB	Output is correct
32	Correct	4 ms	1336 KB	Output is correct
33	Correct	4 ms	1340 KB	Output is correct

Subtask #5
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	1 ms	600 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	344 KB	Output is correct
18	Correct	4 ms	1852 KB	Output is correct
19	Correct	3 ms	1880 KB	Output is correct
20	Correct	3 ms	1884 KB	Output is correct
21	Correct	3 ms	1748 KB	Output is correct
22	Correct	3 ms	1884 KB	Output is correct
23	Correct	3 ms	2136 KB	Output is correct
24	Correct	4 ms	1832 KB	Output is correct
25	Incorrect	126 ms	61328 KB	Output isn't correct
26	Halted	0 ms	0 KB	-

Subtask #6
23.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	166 ms	42544 KB	Output is correct
4	Correct	199 ms	43092 KB	Output is correct
5	Correct	159 ms	43364 KB	Output is correct

Subtask #7
0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	1 ms	600 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	344 KB	Output is correct
18	Correct	4 ms	1852 KB	Output is correct
19	Correct	3 ms	1880 KB	Output is correct
20	Correct	3 ms	1884 KB	Output is correct
21	Correct	3 ms	1748 KB	Output is correct
22	Correct	3 ms	1884 KB	Output is correct
23	Correct	3 ms	2136 KB	Output is correct
24	Correct	4 ms	1832 KB	Output is correct
25	Correct	0 ms	348 KB	Output is correct
26	Correct	3 ms	1628 KB	Output is correct
27	Correct	3 ms	1628 KB	Output is correct
28	Correct	4 ms	1488 KB	Output is correct
29	Correct	3 ms	1628 KB	Output is correct
30	Correct	3 ms	1372 KB	Output is correct
31	Correct	3 ms	1372 KB	Output is correct
32	Correct	4 ms	1336 KB	Output is correct
33	Correct	4 ms	1340 KB	Output is correct
34	Incorrect	126 ms	61328 KB	Output isn't correct
35	Halted	0 ms	0 KB	-

Submission #945438

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 7.0 / 7.0

Subtask #3 7.0 / 7.0

Subtask #4 10.0 / 10.0

Subtask #5 0 / 20.0

Subtask #6 23.0 / 23.0

Subtask #7 0 / 26.0

Subtask #1
7.0 / 7.0

Subtask #2
7.0 / 7.0

Subtask #3
7.0 / 7.0

Subtask #4
10.0 / 10.0

Subtask #5
0 / 20.0

Subtask #6
23.0 / 23.0

Subtask #7
0 / 26.0