oj.uz

Submission #939383

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

using namespace std;

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

const int maxn = 2*1e5+5;

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

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

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

void make_tree(int v, int l, int r)
{
    if(l==r)
    {
        tree[v].ch = p[pos[r]];
        tree[v].num = pos[r];
        return;
    }
    int 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(int v, int l, int r)
{
    if(!lazy[v]) return;
    tree[v] = {0,0};
    lazy[v*2+0] = 1;
    lazy[v*2+1] = 1;
    lazy[v] = 0;
}

Node query(int v, int l, int r)
{
    push_lazy(v,l,r);
    if(r<ql||qr<l||l>r) return {0,0};
    if(ql<=l&&r<=qr) return tree[v];
    int 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(int v, int l, int 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;
    }
    int 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(int i=1;i<=n;i++) cin >> p[i];
    int a,b;
    for(int i=1;i<n;i++)
    {
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
}

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

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

int lca(int a, int b)
{
    int raz = abs(lvl[a]-lvl[b]);
    for(int 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(int 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(int a, int b)
{
    if(a==0||b==0) return 0;
    return lvl[a]+lvl[b]-2*lvl[lca(a,b)];
}

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

long long rec(int 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(int nb:g[beg.num])
    {
        if(nb==jump[beg.num][0]) continue;
        ql = in[nb];
        qr = ou[nb];
        int xi = beg.num;
        int yi = query(1,1,n).num;
        int 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];
    int xi = beg.num;
    int yi = query(1,1,n).num;
    long long raz = dist(xi,yi);
    if(xi==0||yi==0) return ans;
    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 3 ms 12888 KB Output is correct
2 Correct 6 ms 12892 KB Output is correct
3 Correct 3 ms 12964 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 2 ms 12888 KB Output is correct
8 Correct 2 ms 12888 KB Output is correct
9 Correct 2 ms 12892 KB Output is correct
10 Correct 2 ms 12932 KB Output is correct

Subtask #2
7.0 / 7.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 6 ms 12892 KB Output is correct
3 Correct 3 ms 12964 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 2 ms 12888 KB Output is correct
8 Correct 2 ms 12888 KB Output is correct
9 Correct 2 ms 12892 KB Output is correct
10 Correct 2 ms 12932 KB Output is correct
11 Correct 3 ms 12900 KB Output is correct
12 Correct 2 ms 12892 KB Output is correct
13 Correct 2 ms 12892 KB Output is correct
14 Correct 3 ms 12892 KB Output is correct
15 Correct 2 ms 12892 KB Output is correct
16 Correct 3 ms 12888 KB Output is correct
17 Correct 3 ms 12892 KB Output is correct
18 Correct 6 ms 13916 KB Output is correct
19 Correct 6 ms 13660 KB Output is correct
20 Correct 8 ms 13660 KB Output is correct
21 Correct 6 ms 13404 KB Output is correct
22 Correct 6 ms 13404 KB Output is correct
23 Correct 8 ms 13404 KB Output is correct
24 Correct 7 ms 13404 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 6 ms 12892 KB Output is correct
3 Correct 3 ms 12964 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 2 ms 12888 KB Output is correct
8 Correct 2 ms 12888 KB Output is correct
9 Correct 2 ms 12892 KB Output is correct
10 Correct 2 ms 12932 KB Output is correct
11 Correct 3 ms 12900 KB Output is correct
12 Correct 2 ms 12892 KB Output is correct
13 Correct 2 ms 12892 KB Output is correct
14 Correct 3 ms 12892 KB Output is correct
15 Correct 2 ms 12892 KB Output is correct
16 Correct 3 ms 12888 KB Output is correct
17 Correct 3 ms 12892 KB Output is correct
18 Correct 6 ms 13916 KB Output is correct
19 Correct 6 ms 13660 KB Output is correct
20 Correct 8 ms 13660 KB Output is correct
21 Correct 6 ms 13404 KB Output is correct
22 Correct 6 ms 13404 KB Output is correct
23 Correct 8 ms 13404 KB Output is correct
24 Correct 7 ms 13404 KB Output is correct
25 Correct 2 ms 12888 KB Output is correct
26 Correct 8 ms 13660 KB Output is correct
27 Correct 9 ms 13660 KB Output is correct
28 Correct 8 ms 13660 KB Output is correct
29 Correct 9 ms 13656 KB Output is correct
30 Correct 8 ms 13148 KB Output is correct
31 Correct 7 ms 13148 KB Output is correct
32 Correct 8 ms 13148 KB Output is correct
33 Correct 8 ms 13148 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 6 ms 12892 KB Output is correct
3 Correct 3 ms 12964 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 2 ms 12888 KB Output is correct
8 Correct 2 ms 12888 KB Output is correct
9 Correct 2 ms 12892 KB Output is correct
10 Correct 2 ms 12932 KB Output is correct
11 Correct 3 ms 12900 KB Output is correct
12 Correct 2 ms 12892 KB Output is correct
13 Correct 2 ms 12892 KB Output is correct
14 Correct 3 ms 12892 KB Output is correct
15 Correct 2 ms 12892 KB Output is correct
16 Correct 3 ms 12888 KB Output is correct
17 Correct 3 ms 12892 KB Output is correct
18 Correct 6 ms 13916 KB Output is correct
19 Correct 6 ms 13660 KB Output is correct
20 Correct 8 ms 13660 KB Output is correct
21 Correct 6 ms 13404 KB Output is correct
22 Correct 6 ms 13404 KB Output is correct
23 Correct 8 ms 13404 KB Output is correct
24 Correct 7 ms 13404 KB Output is correct
25 Incorrect 253 ms 68424 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 12892 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Execution timed out 2092 ms 628976 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 6 ms 12892 KB Output is correct
3 Correct 3 ms 12964 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 2 ms 12888 KB Output is correct
8 Correct 2 ms 12888 KB Output is correct
9 Correct 2 ms 12892 KB Output is correct
10 Correct 2 ms 12932 KB Output is correct
11 Correct 3 ms 12900 KB Output is correct
12 Correct 2 ms 12892 KB Output is correct
13 Correct 2 ms 12892 KB Output is correct
14 Correct 3 ms 12892 KB Output is correct
15 Correct 2 ms 12892 KB Output is correct
16 Correct 3 ms 12888 KB Output is correct
17 Correct 3 ms 12892 KB Output is correct
18 Correct 6 ms 13916 KB Output is correct
19 Correct 6 ms 13660 KB Output is correct
20 Correct 8 ms 13660 KB Output is correct
21 Correct 6 ms 13404 KB Output is correct
22 Correct 6 ms 13404 KB Output is correct
23 Correct 8 ms 13404 KB Output is correct
24 Correct 7 ms 13404 KB Output is correct
25 Correct 2 ms 12888 KB Output is correct
26 Correct 8 ms 13660 KB Output is correct
27 Correct 9 ms 13660 KB Output is correct
28 Correct 8 ms 13660 KB Output is correct
29 Correct 9 ms 13656 KB Output is correct
30 Correct 8 ms 13148 KB Output is correct
31 Correct 7 ms 13148 KB Output is correct
32 Correct 8 ms 13148 KB Output is correct
33 Correct 8 ms 13148 KB Output is correct
34 Incorrect 253 ms 68424 KB Output isn't correct
35 Halted 0 ms 0 KB -