oj.uz

Submission #939471

# Submission time Handle Problem Language Result Execution time Memory
939471 2024-03-06T11:47:59 Z serkanrashid Cat Exercise (JOI23_ho_t4) C++14
31 / 100
 2000 ms 506056 KB 
#include <bits/stdc++.h>
#define endl "\n"

using namespace std;

struct Node
{
    long long ch,num;
    Node(){};
    Node(long long chi, long long ni)
    {
        ch = chi;
        num = ni;
    }
};

const long long maxn = 2*1e5+5;

long long n,p[maxn],pos[maxn];
long long in[maxn],ou[maxn];

long long jump[maxn][20],lvl[maxn];

long long lazy[4*maxn];
Node tree[4*maxn];
vector<int>g[maxn];
long long timer,ql,qr;

void make_tree(long long v, long long l, long long r)
{
    if(l==r)
    {
        tree[v].ch = p[pos[r]];
        tree[v].num = pos[r];
        return;
    }
    long long mid = (l+r)/2;
    make_tree(v*2+0,l,mid+0);
    make_tree(v*2+1,mid+1,r);
    if(tree[v*2+0].ch>tree[v*2+1].ch) tree[v] = tree[v*2+0];
    else tree[v] = tree[v*2+1];
}

void push_lazy(long long v, long long l, long long r)
{
    if(!lazy[v]) return;
    tree[v] = {0,0};
    lazy[v*2+0] = 1;
    lazy[v*2+1] = 1;
    lazy[v] = 0;
}

Node query(long long v, long long l, long long r)
{
    push_lazy(v,l,r);
    if(r<ql||qr<l||l>r) return {0,0};
    if(ql<=l&&r<=qr) return tree[v];
    long long mid = (l+r)/2;
    Node q1 = query(v*2+0,l,mid+0);
    Node q2 = query(v*2+1,mid+1,r);
    if(q1.ch>q2.ch) return q1;
    else return q2;
}

void update(long long v, long long l, long long r)
{
    push_lazy(v,l,r);
    if(r<ql||qr<l||l>r) return;
    if(ql<=l&&r<=qr)
    {
        lazy[v] = 1;
        push_lazy(v,l,r);
        return;
    }
    long long mid = (l+r)/2;
    update(v*2+0,l,mid+0);
    update(v*2+1,mid+1,r);
    if(tree[v*2+0].ch>tree[v*2+1].ch) tree[v] = tree[v*2+0];
    else tree[v] = tree[v*2+1];
}

void read()
{
    cin >> n;
    for(long long i=1;i<=n;i++) cin >> p[i];
    long long a,b;
    for(long long i=1;i<n;i++)
    {
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
}

bool cmp(long long p1, long long p2)
{
    return in[p1]<in[p2];
}

void dfs(long long beg, long long par)
{
    in[beg] = ++timer;
    jump[beg][0] = par;
    lvl[beg] = lvl[par]+1;
    for(long long nb:g[beg]) if(nb!=par) dfs(nb,beg);
    ou[beg] = timer;
}

long long lca(long long a, long long b)
{
    if(a==0||b==0) return 0;
    long long raz = abs(lvl[a]-lvl[b]);
    for(long long j=0;j<20;j++)
    {
        if(raz&(1<<j))
        {
            if(lvl[a]>lvl[b]) a = jump[a][j];
            else b = jump[b][j];
        }
    }
    if(a==b) return a;
    for(long long j=19;j>=0;j--)
    {
        if(jump[a][j]!=jump[b][j])
        {
            a = jump[a][j];
            b = jump[b][j];
        }
    }
    return jump[a][0];
}

long long dist(long long a, long long b)
{
    if(a==0||b==0) return 0;
    return lvl[a]+lvl[b]-2*lvl[lca(a,b)];
}

void pre()
{
    dfs(1,1);
    for(long long i=1;i<=n;i++) pos[i] = i;
    sort(pos+1,pos+n+1,cmp);
    make_tree(1,1,n);
    for(long long j=1;j<20;j++)
    {
        for(long long i=1;i<=n;i++)
        {
            jump[i][j] = jump[jump[i][j-1]][j-1];
        }
    }
}

long long rec(long long x)
{
    if(x==0) return 0;
    ql = in[x];
    qr = ou[x];
    Node beg = query(1,1,n);
    if(beg.ch==0) return 0;
    long long ans = 0;
    for(long long nb:g[beg.num])
    {
        if(nb==jump[beg.num][0]) continue;
        ql = in[nb];
        qr = ou[nb];
        long long xi = beg.num;
        long long yi = query(1,1,n).num;
        long long raz = dist(xi,yi);
        ans = max(ans,rec(nb)+raz);
    }
    ql = in[beg.num];
    qr = ou[beg.num];
    update(1,1,n);
    ql = in[x];
    qr = ou[x];
    long long xi = beg.num;
    long long yi = query(1,1,n).num;
    long long raz = dist(xi,yi);
    ans = max(ans,rec(x)+raz);
    return ans;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	read();
	pre();
	cout << rec(1) << endl;
return 0;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14936 KB Output is correct
2 Correct 4 ms 14940 KB Output is correct
3 Correct 2 ms 14940 KB Output is correct
4 Correct 2 ms 14940 KB Output is correct
5 Correct 2 ms 14940 KB Output is correct
6 Correct 2 ms 14936 KB Output is correct
7 Correct 2 ms 14936 KB Output is correct
8 Correct 2 ms 14936 KB Output is correct
9 Correct 3 ms 14940 KB Output is correct
10 Correct 3 ms 14940 KB Output is correct
11 Correct 3 ms 14940 KB Output is correct
12 Correct 3 ms 14940 KB Output is correct
13 Correct 3 ms 14940 KB Output is correct
14 Correct 3 ms 14940 KB Output is correct
15 Correct 5 ms 14940 KB Output is correct
16 Correct 3 ms 14936 KB Output is correct
17 Correct 3 ms 14940 KB Output is correct
18 Correct 8 ms 15708 KB Output is correct
19 Correct 7 ms 15960 KB Output is correct
20 Correct 7 ms 15708 KB Output is correct
21 Correct 7 ms 15692 KB Output is correct
22 Correct 7 ms 15452 KB Output is correct
23 Correct 7 ms 15452 KB Output is correct
24 Correct 7 ms 15564 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14936 KB Output is correct
2 Correct 4 ms 14940 KB Output is correct
3 Correct 2 ms 14940 KB Output is correct
4 Correct 2 ms 14940 KB Output is correct
5 Correct 2 ms 14940 KB Output is correct
6 Correct 2 ms 14936 KB Output is correct
7 Correct 2 ms 14936 KB Output is correct
8 Correct 2 ms 14936 KB Output is correct
9 Correct 3 ms 14940 KB Output is correct
10 Correct 3 ms 14940 KB Output is correct
11 Correct 3 ms 14940 KB Output is correct
12 Correct 3 ms 14940 KB Output is correct
13 Correct 3 ms 14940 KB Output is correct
14 Correct 3 ms 14940 KB Output is correct
15 Correct 5 ms 14940 KB Output is correct
16 Correct 3 ms 14936 KB Output is correct
17 Correct 3 ms 14940 KB Output is correct
18 Correct 8 ms 15708 KB Output is correct
19 Correct 7 ms 15960 KB Output is correct
20 Correct 7 ms 15708 KB Output is correct
21 Correct 7 ms 15692 KB Output is correct
22 Correct 7 ms 15452 KB Output is correct
23 Correct 7 ms 15452 KB Output is correct
24 Correct 7 ms 15564 KB Output is correct
25 Correct 3 ms 14940 KB Output is correct
26 Correct 8 ms 15672 KB Output is correct
27 Correct 9 ms 15704 KB Output is correct
28 Correct 9 ms 15708 KB Output is correct
29 Correct 9 ms 15708 KB Output is correct
30 Correct 9 ms 15264 KB Output is correct
31 Correct 9 ms 15452 KB Output is correct
32 Correct 8 ms 15452 KB Output is correct
33 Correct 9 ms 15372 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14936 KB Output is correct
2 Correct 4 ms 14940 KB Output is correct
3 Correct 2 ms 14940 KB Output is correct
4 Correct 2 ms 14940 KB Output is correct
5 Correct 2 ms 14940 KB Output is correct
6 Correct 2 ms 14936 KB Output is correct
7 Correct 2 ms 14936 KB Output is correct
8 Correct 2 ms 14936 KB Output is correct
9 Correct 3 ms 14940 KB Output is correct
10 Correct 3 ms 14940 KB Output is correct
11 Correct 3 ms 14940 KB Output is correct
12 Correct 3 ms 14940 KB Output is correct
13 Correct 3 ms 14940 KB Output is correct
14 Correct 3 ms 14940 KB Output is correct
15 Correct 5 ms 14940 KB Output is correct
16 Correct 3 ms 14936 KB Output is correct
17 Correct 3 ms 14940 KB Output is correct
18 Correct 8 ms 15708 KB Output is correct
19 Correct 7 ms 15960 KB Output is correct
20 Correct 7 ms 15708 KB Output is correct
21 Correct 7 ms 15692 KB Output is correct
22 Correct 7 ms 15452 KB Output is correct
23 Correct 7 ms 15452 KB Output is correct
24 Correct 7 ms 15564 KB Output is correct
25 Incorrect 304 ms 85272 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14936 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Execution timed out 2101 ms 506056 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14936 KB Output is correct
2 Correct 4 ms 14940 KB Output is correct
3 Correct 2 ms 14940 KB Output is correct
4 Correct 2 ms 14940 KB Output is correct
5 Correct 2 ms 14940 KB Output is correct
6 Correct 2 ms 14936 KB Output is correct
7 Correct 2 ms 14936 KB Output is correct
8 Correct 2 ms 14936 KB Output is correct
9 Correct 3 ms 14940 KB Output is correct
10 Correct 3 ms 14940 KB Output is correct
11 Correct 3 ms 14940 KB Output is correct
12 Correct 3 ms 14940 KB Output is correct
13 Correct 3 ms 14940 KB Output is correct
14 Correct 3 ms 14940 KB Output is correct
15 Correct 5 ms 14940 KB Output is correct
16 Correct 3 ms 14936 KB Output is correct
17 Correct 3 ms 14940 KB Output is correct
18 Correct 8 ms 15708 KB Output is correct
19 Correct 7 ms 15960 KB Output is correct
20 Correct 7 ms 15708 KB Output is correct
21 Correct 7 ms 15692 KB Output is correct
22 Correct 7 ms 15452 KB Output is correct
23 Correct 7 ms 15452 KB Output is correct
24 Correct 7 ms 15564 KB Output is correct
25 Correct 3 ms 14940 KB Output is correct
26 Correct 8 ms 15672 KB Output is correct
27 Correct 9 ms 15704 KB Output is correct
28 Correct 9 ms 15708 KB Output is correct
29 Correct 9 ms 15708 KB Output is correct
30 Correct 9 ms 15264 KB Output is correct
31 Correct 9 ms 15452 KB Output is correct
32 Correct 8 ms 15452 KB Output is correct
33 Correct 9 ms 15372 KB Output is correct
34 Incorrect 304 ms 85272 KB Output isn't correct
35 Halted 0 ms 0 KB -