답안 #919665

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
919665	2024-02-01T11:15:27 Z	andrei_iorgulescu	Cat Exercise (JOI23_ho_t4)	C++14	54 / 100	171 ms	50256 KB

Main

#include <bits/stdc++.h>

using namespace std;

int n,p[200005],pos[200005];
vector<int>g[200005];
int bl[20][200005];
int lg[200005];
int tt[200005],sz[200005];
int cine[200005];
int h[200005],t[200005];
int dp[200005];

void dfs(int nod,int tata)
{
    for (auto vecin : g[nod])
    {
        if (vecin != tata)
        {
            h[vecin] = 1 + h[nod];
            t[vecin] = nod;
            dfs(vecin,nod);
        }
    }
}

int root(int x)
{
    while (x != tt[x])
        x = tt[x];
    return x;
}

void unite(int x,int y)
{
    x = root(x);
    y = root(y);
    if (x == y)
        return;
    if (sz[x] < sz[y])
        swap(x,y);
    tt[y] = x;
    sz[x] += sz[y];
    if (p[cine[y]] > p[cine[x]])
        cine[x] = cine[y];
}

int lca(int x,int y)
{
    if (h[x] > h[y])
        swap(x,y);
    for (int st = lg[n]; st >= 0; st--)
        if (h[y] - (1 << st) >= h[x])
            y = bl[st][y];
    if (x == y)
        return x;
    for (int st = lg[n]; st >= 0; st--)
        if (bl[st][x] != bl[st][y])
            x = bl[st][x],y = bl[st][y];
    return t[x];
}

int dist(int x,int y)
{
    return h[x] + h[y] - 2 * h[lca(x,y)];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> p[i],pos[p[i]] = i;
    for (int i = 1; i <= n; i++)
        tt[i] = i,sz[i] = 1,cine[i] = i;
    for (int i = 1; i < n; i++)
    {
        int x,y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1,0);
    for (int i = 2; i <= n; i++)
        lg[i] = 1 + lg[i / 2];
    for (int i = 1; i <= n; i++)
        bl[0][i] = t[i];
    for (int j = 1; j <= lg[n]; j++)
        for (int i = 1; i <= n; i++)
            bl[j][i] = bl[j - 1][bl[j - 1][i]];
    for (int i = 1; i <= n; i++)
    {
        int nod = pos[i];
        for (auto vecin : g[nod])
        {
            if (p[vecin] < p[nod])
            {
                int x = cine[root(vecin)];
                dp[nod] = max(dp[nod],dp[x] + dist(nod,x));
                unite(nod,vecin);
            }
        }
    }
    cout << dp[pos[n]];
    return 0;
}

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	10584 KB	Output is correct
2	Correct	2 ms	10588 KB	Output is correct
3	Correct	3 ms	10584 KB	Output is correct
4	Correct	4 ms	12792 KB	Output is correct
5	Correct	3 ms	12632 KB	Output is correct
6	Correct	3 ms	12632 KB	Output is correct
7	Correct	2 ms	8536 KB	Output is correct
8	Correct	3 ms	12632 KB	Output is correct
9	Correct	4 ms	12632 KB	Output is correct
10	Correct	3 ms	12636 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	10584 KB	Output is correct
2	Correct	2 ms	10588 KB	Output is correct
3	Correct	3 ms	10584 KB	Output is correct
4	Correct	4 ms	12792 KB	Output is correct
5	Correct	3 ms	12632 KB	Output is correct
6	Correct	3 ms	12632 KB	Output is correct
7	Correct	2 ms	8536 KB	Output is correct
8	Correct	3 ms	12632 KB	Output is correct
9	Correct	4 ms	12632 KB	Output is correct
10	Correct	3 ms	12636 KB	Output is correct
11	Correct	4 ms	14680 KB	Output is correct
12	Correct	3 ms	12636 KB	Output is correct
13	Correct	4 ms	14680 KB	Output is correct
14	Correct	3 ms	14680 KB	Output is correct
15	Correct	4 ms	14680 KB	Output is correct
16	Correct	3 ms	14680 KB	Output is correct
17	Correct	4 ms	14684 KB	Output is correct

Subtask #3
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	10584 KB	Output is correct
2	Correct	2 ms	10588 KB	Output is correct
3	Correct	3 ms	10584 KB	Output is correct
4	Correct	4 ms	12792 KB	Output is correct
5	Correct	3 ms	12632 KB	Output is correct
6	Correct	3 ms	12632 KB	Output is correct
7	Correct	2 ms	8536 KB	Output is correct
8	Correct	3 ms	12632 KB	Output is correct
9	Correct	4 ms	12632 KB	Output is correct
10	Correct	3 ms	12636 KB	Output is correct
11	Correct	4 ms	14680 KB	Output is correct
12	Correct	3 ms	12636 KB	Output is correct
13	Correct	4 ms	14680 KB	Output is correct
14	Correct	3 ms	14680 KB	Output is correct
15	Correct	4 ms	14680 KB	Output is correct
16	Correct	3 ms	14680 KB	Output is correct
17	Correct	4 ms	14684 KB	Output is correct
18	Correct	6 ms	19576 KB	Output is correct
19	Correct	5 ms	19544 KB	Output is correct
20	Correct	6 ms	19548 KB	Output is correct
21	Correct	5 ms	19544 KB	Output is correct
22	Correct	5 ms	19548 KB	Output is correct
23	Correct	5 ms	19548 KB	Output is correct
24	Correct	5 ms	19544 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	10584 KB	Output is correct
2	Correct	2 ms	10588 KB	Output is correct
3	Correct	3 ms	10584 KB	Output is correct
4	Correct	4 ms	12792 KB	Output is correct
5	Correct	3 ms	12632 KB	Output is correct
6	Correct	3 ms	12632 KB	Output is correct
7	Correct	2 ms	8536 KB	Output is correct
8	Correct	3 ms	12632 KB	Output is correct
9	Correct	4 ms	12632 KB	Output is correct
10	Correct	3 ms	12636 KB	Output is correct
11	Correct	4 ms	14680 KB	Output is correct
12	Correct	3 ms	12636 KB	Output is correct
13	Correct	4 ms	14680 KB	Output is correct
14	Correct	3 ms	14680 KB	Output is correct
15	Correct	4 ms	14680 KB	Output is correct
16	Correct	3 ms	14680 KB	Output is correct
17	Correct	4 ms	14684 KB	Output is correct
18	Correct	6 ms	19576 KB	Output is correct
19	Correct	5 ms	19544 KB	Output is correct
20	Correct	6 ms	19548 KB	Output is correct
21	Correct	5 ms	19544 KB	Output is correct
22	Correct	5 ms	19548 KB	Output is correct
23	Correct	5 ms	19548 KB	Output is correct
24	Correct	5 ms	19544 KB	Output is correct
25	Correct	2 ms	10588 KB	Output is correct
26	Correct	6 ms	19288 KB	Output is correct
27	Correct	6 ms	19292 KB	Output is correct
28	Correct	6 ms	19292 KB	Output is correct
29	Correct	6 ms	19288 KB	Output is correct
30	Correct	6 ms	19292 KB	Output is correct
31	Correct	6 ms	19288 KB	Output is correct
32	Correct	6 ms	19236 KB	Output is correct
33	Correct	7 ms	19292 KB	Output is correct

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	10584 KB	Output is correct
2	Correct	2 ms	10588 KB	Output is correct
3	Correct	3 ms	10584 KB	Output is correct
4	Correct	4 ms	12792 KB	Output is correct
5	Correct	3 ms	12632 KB	Output is correct
6	Correct	3 ms	12632 KB	Output is correct
7	Correct	2 ms	8536 KB	Output is correct
8	Correct	3 ms	12632 KB	Output is correct
9	Correct	4 ms	12632 KB	Output is correct
10	Correct	3 ms	12636 KB	Output is correct
11	Correct	4 ms	14680 KB	Output is correct
12	Correct	3 ms	12636 KB	Output is correct
13	Correct	4 ms	14680 KB	Output is correct
14	Correct	3 ms	14680 KB	Output is correct
15	Correct	4 ms	14680 KB	Output is correct
16	Correct	3 ms	14680 KB	Output is correct
17	Correct	4 ms	14684 KB	Output is correct
18	Correct	6 ms	19576 KB	Output is correct
19	Correct	5 ms	19544 KB	Output is correct
20	Correct	6 ms	19548 KB	Output is correct
21	Correct	5 ms	19544 KB	Output is correct
22	Correct	5 ms	19548 KB	Output is correct
23	Correct	5 ms	19548 KB	Output is correct
24	Correct	5 ms	19544 KB	Output is correct
25	Incorrect	95 ms	50256 KB	Output isn't correct
26	Halted	0 ms	0 KB	-

Subtask #6
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	10584 KB	Output is correct
2	Correct	3 ms	14680 KB	Output is correct
3	Correct	171 ms	37708 KB	Output is correct
4	Correct	149 ms	37756 KB	Output is correct
5	Correct	147 ms	37712 KB	Output is correct

Subtask #7
0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	10584 KB	Output is correct
2	Correct	2 ms	10588 KB	Output is correct
3	Correct	3 ms	10584 KB	Output is correct
4	Correct	4 ms	12792 KB	Output is correct
5	Correct	3 ms	12632 KB	Output is correct
6	Correct	3 ms	12632 KB	Output is correct
7	Correct	2 ms	8536 KB	Output is correct
8	Correct	3 ms	12632 KB	Output is correct
9	Correct	4 ms	12632 KB	Output is correct
10	Correct	3 ms	12636 KB	Output is correct
11	Correct	4 ms	14680 KB	Output is correct
12	Correct	3 ms	12636 KB	Output is correct
13	Correct	4 ms	14680 KB	Output is correct
14	Correct	3 ms	14680 KB	Output is correct
15	Correct	4 ms	14680 KB	Output is correct
16	Correct	3 ms	14680 KB	Output is correct
17	Correct	4 ms	14684 KB	Output is correct
18	Correct	6 ms	19576 KB	Output is correct
19	Correct	5 ms	19544 KB	Output is correct
20	Correct	6 ms	19548 KB	Output is correct
21	Correct	5 ms	19544 KB	Output is correct
22	Correct	5 ms	19548 KB	Output is correct
23	Correct	5 ms	19548 KB	Output is correct
24	Correct	5 ms	19544 KB	Output is correct
25	Correct	2 ms	10588 KB	Output is correct
26	Correct	6 ms	19288 KB	Output is correct
27	Correct	6 ms	19292 KB	Output is correct
28	Correct	6 ms	19292 KB	Output is correct
29	Correct	6 ms	19288 KB	Output is correct
30	Correct	6 ms	19292 KB	Output is correct
31	Correct	6 ms	19288 KB	Output is correct
32	Correct	6 ms	19236 KB	Output is correct
33	Correct	7 ms	19292 KB	Output is correct
34	Incorrect	95 ms	50256 KB	Output isn't correct
35	Halted	0 ms	0 KB	-

답안 #919665

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