답안 #1094915

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1094915	2024-09-30T20:46:59 Z	Nom_mxmx	Cat Exercise (JOI23_ho_t4)	C++14	54 / 100	153 ms	43988 KB

Main

#include <bits/stdc++.h>
using namespace std;

#define nl '\n'
#define pb push_back

const int N = 2e5+3;
vector<int> g[N];
int w[N];
int p[N];
int d[N];
int rep[N];
int mx[N];
int dp[N];
int jmp[N][20];

int Find(int a) {
    return (rep[a] == a)? a : rep[a] = Find(rep[a]);
}

void Union(int a, int b) {
    a = Find(a), b = Find(b);
    rep[b] = a;
}

void dfs(int v, int p) {
    d[v] = d[p]+1;
    jmp[v][0] = p;

    for(int i=1; i<20; i++)
        jmp[v][i] = jmp[jmp[v][i-1]][i-1];

    for(auto u:g[v]) {
        if(u == p) continue;
        dfs(u, v);
    }
}

int lca(int a, int b) {
    if(d[a] < d[b]) swap(a, b);

    for(int i=19; i>=0; i--) {
        if(d[jmp[a][i]] >= d[b])
            a = jmp[a][i];
    }
    for(int i=19; i>=0; i--) {
        if(jmp[a][i] != jmp[b][i]) {
            a = jmp[a][i];
            b = jmp[b][i];
        }
    }
    if(a == b) return a;
    return jmp[a][0];
}

int dist(int a, int b) {
    return d[a] + d[b] - 2*d[lca(a, b)];
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    for(int i=1; i<=n; i++) {
        cin >> w[i];
        p[w[i]] = i;
        rep[i] = i;
    }

    for(int i=1; i<n; i++) {
        int a, b;
        cin >> a >> b;

        g[a].pb(b);
        g[b].pb(a);
    }

    dfs(1, 0);
    for(int i=1; i<=n; i++) {
        int v = p[i];

        for(auto u:g[v]) {
            if(w[v] > w[u]) {
                int a = Find(u);

                dp[v] = max(dp[v], dp[a] + dist(v, a));
                Union(v, a); // v > a 
            }
        }
    }

    cout << dp[p[n]];
}

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4956 KB	Output is correct
2	Correct	2 ms	4956 KB	Output is correct
3	Correct	2 ms	5160 KB	Output is correct
4	Correct	2 ms	4956 KB	Output is correct
5	Correct	2 ms	5168 KB	Output is correct
6	Correct	2 ms	4956 KB	Output is correct
7	Correct	2 ms	4952 KB	Output is correct
8	Correct	2 ms	4956 KB	Output is correct
9	Correct	2 ms	4956 KB	Output is correct
10	Correct	2 ms	4956 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4956 KB	Output is correct
2	Correct	2 ms	4956 KB	Output is correct
3	Correct	2 ms	5160 KB	Output is correct
4	Correct	2 ms	4956 KB	Output is correct
5	Correct	2 ms	5168 KB	Output is correct
6	Correct	2 ms	4956 KB	Output is correct
7	Correct	2 ms	4952 KB	Output is correct
8	Correct	2 ms	4956 KB	Output is correct
9	Correct	2 ms	4956 KB	Output is correct
10	Correct	2 ms	4956 KB	Output is correct
11	Correct	2 ms	5212 KB	Output is correct
12	Correct	2 ms	5212 KB	Output is correct
13	Correct	3 ms	5212 KB	Output is correct
14	Correct	2 ms	4996 KB	Output is correct
15	Correct	2 ms	5208 KB	Output is correct
16	Correct	2 ms	5212 KB	Output is correct
17	Correct	2 ms	5212 KB	Output is correct

Subtask #3
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4956 KB	Output is correct
2	Correct	2 ms	4956 KB	Output is correct
3	Correct	2 ms	5160 KB	Output is correct
4	Correct	2 ms	4956 KB	Output is correct
5	Correct	2 ms	5168 KB	Output is correct
6	Correct	2 ms	4956 KB	Output is correct
7	Correct	2 ms	4952 KB	Output is correct
8	Correct	2 ms	4956 KB	Output is correct
9	Correct	2 ms	4956 KB	Output is correct
10	Correct	2 ms	4956 KB	Output is correct
11	Correct	2 ms	5212 KB	Output is correct
12	Correct	2 ms	5212 KB	Output is correct
13	Correct	3 ms	5212 KB	Output is correct
14	Correct	2 ms	4996 KB	Output is correct
15	Correct	2 ms	5208 KB	Output is correct
16	Correct	2 ms	5212 KB	Output is correct
17	Correct	2 ms	5212 KB	Output is correct
18	Correct	5 ms	5980 KB	Output is correct
19	Correct	5 ms	6060 KB	Output is correct
20	Correct	4 ms	5980 KB	Output is correct
21	Correct	4 ms	5980 KB	Output is correct
22	Correct	4 ms	5980 KB	Output is correct
23	Correct	4 ms	5980 KB	Output is correct
24	Correct	4 ms	5980 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4956 KB	Output is correct
2	Correct	2 ms	4956 KB	Output is correct
3	Correct	2 ms	5160 KB	Output is correct
4	Correct	2 ms	4956 KB	Output is correct
5	Correct	2 ms	5168 KB	Output is correct
6	Correct	2 ms	4956 KB	Output is correct
7	Correct	2 ms	4952 KB	Output is correct
8	Correct	2 ms	4956 KB	Output is correct
9	Correct	2 ms	4956 KB	Output is correct
10	Correct	2 ms	4956 KB	Output is correct
11	Correct	2 ms	5212 KB	Output is correct
12	Correct	2 ms	5212 KB	Output is correct
13	Correct	3 ms	5212 KB	Output is correct
14	Correct	2 ms	4996 KB	Output is correct
15	Correct	2 ms	5208 KB	Output is correct
16	Correct	2 ms	5212 KB	Output is correct
17	Correct	2 ms	5212 KB	Output is correct
18	Correct	5 ms	5980 KB	Output is correct
19	Correct	5 ms	6060 KB	Output is correct
20	Correct	4 ms	5980 KB	Output is correct
21	Correct	4 ms	5980 KB	Output is correct
22	Correct	4 ms	5980 KB	Output is correct
23	Correct	4 ms	5980 KB	Output is correct
24	Correct	4 ms	5980 KB	Output is correct
25	Correct	2 ms	4956 KB	Output is correct
26	Correct	4 ms	5944 KB	Output is correct
27	Correct	5 ms	5976 KB	Output is correct
28	Correct	5 ms	5944 KB	Output is correct
29	Correct	5 ms	5980 KB	Output is correct
30	Correct	5 ms	5720 KB	Output is correct
31	Correct	7 ms	5720 KB	Output is correct
32	Correct	4 ms	5724 KB	Output is correct
33	Correct	5 ms	5720 KB	Output is correct

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4956 KB	Output is correct
2	Correct	2 ms	4956 KB	Output is correct
3	Correct	2 ms	5160 KB	Output is correct
4	Correct	2 ms	4956 KB	Output is correct
5	Correct	2 ms	5168 KB	Output is correct
6	Correct	2 ms	4956 KB	Output is correct
7	Correct	2 ms	4952 KB	Output is correct
8	Correct	2 ms	4956 KB	Output is correct
9	Correct	2 ms	4956 KB	Output is correct
10	Correct	2 ms	4956 KB	Output is correct
11	Correct	2 ms	5212 KB	Output is correct
12	Correct	2 ms	5212 KB	Output is correct
13	Correct	3 ms	5212 KB	Output is correct
14	Correct	2 ms	4996 KB	Output is correct
15	Correct	2 ms	5208 KB	Output is correct
16	Correct	2 ms	5212 KB	Output is correct
17	Correct	2 ms	5212 KB	Output is correct
18	Correct	5 ms	5980 KB	Output is correct
19	Correct	5 ms	6060 KB	Output is correct
20	Correct	4 ms	5980 KB	Output is correct
21	Correct	4 ms	5980 KB	Output is correct
22	Correct	4 ms	5980 KB	Output is correct
23	Correct	4 ms	5980 KB	Output is correct
24	Correct	4 ms	5980 KB	Output is correct
25	Incorrect	100 ms	43988 KB	Output isn't correct
26	Halted	0 ms	0 KB	-

Subtask #6
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4952 KB	Output is correct
2	Correct	2 ms	5212 KB	Output is correct
3	Correct	153 ms	34440 KB	Output is correct
4	Correct	142 ms	34436 KB	Output is correct
5	Correct	135 ms	34424 KB	Output is correct

Subtask #7
0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4956 KB	Output is correct
2	Correct	2 ms	4956 KB	Output is correct
3	Correct	2 ms	5160 KB	Output is correct
4	Correct	2 ms	4956 KB	Output is correct
5	Correct	2 ms	5168 KB	Output is correct
6	Correct	2 ms	4956 KB	Output is correct
7	Correct	2 ms	4952 KB	Output is correct
8	Correct	2 ms	4956 KB	Output is correct
9	Correct	2 ms	4956 KB	Output is correct
10	Correct	2 ms	4956 KB	Output is correct
11	Correct	2 ms	5212 KB	Output is correct
12	Correct	2 ms	5212 KB	Output is correct
13	Correct	3 ms	5212 KB	Output is correct
14	Correct	2 ms	4996 KB	Output is correct
15	Correct	2 ms	5208 KB	Output is correct
16	Correct	2 ms	5212 KB	Output is correct
17	Correct	2 ms	5212 KB	Output is correct
18	Correct	5 ms	5980 KB	Output is correct
19	Correct	5 ms	6060 KB	Output is correct
20	Correct	4 ms	5980 KB	Output is correct
21	Correct	4 ms	5980 KB	Output is correct
22	Correct	4 ms	5980 KB	Output is correct
23	Correct	4 ms	5980 KB	Output is correct
24	Correct	4 ms	5980 KB	Output is correct
25	Correct	2 ms	4956 KB	Output is correct
26	Correct	4 ms	5944 KB	Output is correct
27	Correct	5 ms	5976 KB	Output is correct
28	Correct	5 ms	5944 KB	Output is correct
29	Correct	5 ms	5980 KB	Output is correct
30	Correct	5 ms	5720 KB	Output is correct
31	Correct	7 ms	5720 KB	Output is correct
32	Correct	4 ms	5724 KB	Output is correct
33	Correct	5 ms	5720 KB	Output is correct
34	Incorrect	100 ms	43988 KB	Output isn't correct
35	Halted	0 ms	0 KB	-

답안 #1094915

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