oj.uz

Submission #919665

# Submission time Handle Problem Language Result Execution time Memory
919665 2024-02-01T11:15:27 Z andrei_iorgulescu Cat Exercise (JOI23_ho_t4) C++14
54 / 100
 171 ms 50256 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -