oj.uz

Submission #1067093

# Submission time Handle Problem Language Result Execution time Memory
1067093 2024-08-20T11:09:55 Z Dennis_Jason Cat Exercise (JOI23_ho_t4) C++14
54 / 100
 195 ms 48512 KB 
#include <bits/stdc++.h>

//#define int long long
#define pb push_back
#define eb emplace_back
#define MOD 1000000007
#define nl '\n'
#define INF  1000000007
#define LLONG_MAX 9223372036854775807
#define pii pair<int,int>
#define tpl tuple<int,int,int,int>
//#pragma GCC optimize("O3")
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
/*
 *
 *
    ----------------DEMONSTRATION-------------------

    ---------------------END------------------------
 */
#define NMAX 200001
int n;
vector<int>v;
vector<vector<int>>G(NMAX);

struct LCA{

    int depth[NMAX];
    int tata[NMAX][20];
    void dfs(int node,int parent,int dep)
    {
        depth[node]=dep;
        tata[node][0]=parent;
        for(auto x:G[node])
        {
            if(x!=parent)
            {
                dfs(x,node,dep+1);
            }
        }
    }

    void init()
    {
        dfs(1,0,0);
        for(int d=0;d<19;++d)
        {
            for(int i=1;i<=n;++i)
            {
                tata[i][d+1]=tata[tata[i][d]][d];
            }
        }
    }

    int lca(int a,int b)
    {
        if(depth[a]>depth[b])
            swap(a,b);
        for(int d=19;d>=0;--d)
        {
            if(depth[a]<=depth[b]-(1<<d))
            {
                b=tata[b][d];
            }
        }

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

        return tata[a][0];
    }

    int dist(int a,int b)
    {
        int c=lca(a,b);
        return depth[a]+depth[b]-2*depth[c];
    }
};
LCA lca;
struct UnionFind{
    int tata[NMAX];
    void init()
    {
        for(int i=1;i<=n;++i)
            tata[i]=i;
    }

    int root(int a)
    {
        if(a==tata[a])
            return a;
        else
            return tata[a]=root(tata[a]);
    }

    void unite(int a,int b)
    {
        a=root(a);
        b=root(b);
        if(a!=b)
        {
            if(v[a]>v[b])
                swap(a,b);
            tata[a]=b;
        }
    }
};
UnionFind kruskal;
signed main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>n;
    v.resize(n+1);
    int root;
    map<int,int>mp;
    for(int i=1;i<=n;++i)
    {
        cin>>v[i];
        mp[v[i]]=i;
    }

    for(int i=1;i<n;++i)
    {
        int x,y;
        cin>>x>>y;
        G[x].pb(y);
        G[y].pb(x);
    }
   lca.init();
    kruskal.init();
    vector<int>dp(n+1,0);
    for(int i=1;i<=n;++i)
    {
        int x=mp[i];
        int ans=0;
        for(auto z:G[x])
        {
            if(v[z]<v[x])
            {
                int v=kruskal.root(z);
                ans=max(ans,dp[v]+lca.dist(v,x));
                kruskal.unite(x,z);
            }
        }
        dp[x]=ans;
    }
    root=mp[n];
    cout<<dp[root];
    return 0;
}

Compilation message

Main.cpp:9: warning: "LLONG_MAX" redefined
    9 | #define LLONG_MAX 9223372036854775807
      | 
In file included from /usr/lib/gcc/x86_64-linux-gnu/10/include/limits.h:195,
                 from /usr/lib/gcc/x86_64-linux-gnu/10/include/syslimits.h:7,
                 from /usr/lib/gcc/x86_64-linux-gnu/10/include/limits.h:34,
                 from /usr/include/c++/10/climits:42,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:39,
                 from Main.cpp:1:
/usr/include/limits.h:135: note: this is the location of the previous definition
  135 | #  define LLONG_MAX __LONG_LONG_MAX__
      |

Subtask #1
7.0 / 7.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7004 KB Output is correct
2 Correct 1 ms 7004 KB Output is correct
3 Correct 1 ms 7004 KB Output is correct
4 Correct 1 ms 7004 KB Output is correct
5 Correct 2 ms 7004 KB Output is correct
6 Correct 1 ms 7004 KB Output is correct
7 Correct 1 ms 7004 KB Output is correct
8 Correct 1 ms 7000 KB Output is correct
9 Correct 2 ms 7004 KB Output is correct
10 Correct 2 ms 7004 KB Output is correct
11 Correct 2 ms 7004 KB Output is correct
12 Correct 2 ms 7004 KB Output is correct
13 Correct 2 ms 7004 KB Output is correct
14 Correct 2 ms 7004 KB Output is correct
15 Correct 3 ms 7260 KB Output is correct
16 Correct 2 ms 7260 KB Output is correct
17 Correct 2 ms 7004 KB Output is correct
18 Correct 3 ms 7772 KB Output is correct
19 Correct 4 ms 7772 KB Output is correct
20 Correct 4 ms 7772 KB Output is correct
21 Correct 6 ms 7680 KB Output is correct
22 Correct 5 ms 7772 KB Output is correct
23 Correct 4 ms 7772 KB Output is correct
24 Correct 4 ms 7772 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7004 KB Output is correct
2 Correct 1 ms 7004 KB Output is correct
3 Correct 1 ms 7004 KB Output is correct
4 Correct 1 ms 7004 KB Output is correct
5 Correct 2 ms 7004 KB Output is correct
6 Correct 1 ms 7004 KB Output is correct
7 Correct 1 ms 7004 KB Output is correct
8 Correct 1 ms 7000 KB Output is correct
9 Correct 2 ms 7004 KB Output is correct
10 Correct 2 ms 7004 KB Output is correct
11 Correct 2 ms 7004 KB Output is correct
12 Correct 2 ms 7004 KB Output is correct
13 Correct 2 ms 7004 KB Output is correct
14 Correct 2 ms 7004 KB Output is correct
15 Correct 3 ms 7260 KB Output is correct
16 Correct 2 ms 7260 KB Output is correct
17 Correct 2 ms 7004 KB Output is correct
18 Correct 3 ms 7772 KB Output is correct
19 Correct 4 ms 7772 KB Output is correct
20 Correct 4 ms 7772 KB Output is correct
21 Correct 6 ms 7680 KB Output is correct
22 Correct 5 ms 7772 KB Output is correct
23 Correct 4 ms 7772 KB Output is correct
24 Correct 4 ms 7772 KB Output is correct
25 Correct 1 ms 7004 KB Output is correct
26 Correct 4 ms 7772 KB Output is correct
27 Correct 4 ms 7772 KB Output is correct
28 Correct 5 ms 7756 KB Output is correct
29 Correct 5 ms 7652 KB Output is correct
30 Correct 4 ms 7516 KB Output is correct
31 Correct 5 ms 7728 KB Output is correct
32 Correct 5 ms 7512 KB Output is correct
33 Correct 4 ms 7516 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7004 KB Output is correct
2 Correct 1 ms 7004 KB Output is correct
3 Correct 1 ms 7004 KB Output is correct
4 Correct 1 ms 7004 KB Output is correct
5 Correct 2 ms 7004 KB Output is correct
6 Correct 1 ms 7004 KB Output is correct
7 Correct 1 ms 7004 KB Output is correct
8 Correct 1 ms 7000 KB Output is correct
9 Correct 2 ms 7004 KB Output is correct
10 Correct 2 ms 7004 KB Output is correct
11 Correct 2 ms 7004 KB Output is correct
12 Correct 2 ms 7004 KB Output is correct
13 Correct 2 ms 7004 KB Output is correct
14 Correct 2 ms 7004 KB Output is correct
15 Correct 3 ms 7260 KB Output is correct
16 Correct 2 ms 7260 KB Output is correct
17 Correct 2 ms 7004 KB Output is correct
18 Correct 3 ms 7772 KB Output is correct
19 Correct 4 ms 7772 KB Output is correct
20 Correct 4 ms 7772 KB Output is correct
21 Correct 6 ms 7680 KB Output is correct
22 Correct 5 ms 7772 KB Output is correct
23 Correct 4 ms 7772 KB Output is correct
24 Correct 4 ms 7772 KB Output is correct
25 Incorrect 112 ms 48512 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 2 ms 7004 KB Output is correct
2 Correct 2 ms 7004 KB Output is correct
3 Correct 195 ms 41680 KB Output is correct
4 Correct 193 ms 43344 KB Output is correct
5 Correct 193 ms 43128 KB Output is correct

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7004 KB Output is correct
2 Correct 1 ms 7004 KB Output is correct
3 Correct 1 ms 7004 KB Output is correct
4 Correct 1 ms 7004 KB Output is correct
5 Correct 2 ms 7004 KB Output is correct
6 Correct 1 ms 7004 KB Output is correct
7 Correct 1 ms 7004 KB Output is correct
8 Correct 1 ms 7000 KB Output is correct
9 Correct 2 ms 7004 KB Output is correct
10 Correct 2 ms 7004 KB Output is correct
11 Correct 2 ms 7004 KB Output is correct
12 Correct 2 ms 7004 KB Output is correct
13 Correct 2 ms 7004 KB Output is correct
14 Correct 2 ms 7004 KB Output is correct
15 Correct 3 ms 7260 KB Output is correct
16 Correct 2 ms 7260 KB Output is correct
17 Correct 2 ms 7004 KB Output is correct
18 Correct 3 ms 7772 KB Output is correct
19 Correct 4 ms 7772 KB Output is correct
20 Correct 4 ms 7772 KB Output is correct
21 Correct 6 ms 7680 KB Output is correct
22 Correct 5 ms 7772 KB Output is correct
23 Correct 4 ms 7772 KB Output is correct
24 Correct 4 ms 7772 KB Output is correct
25 Correct 1 ms 7004 KB Output is correct
26 Correct 4 ms 7772 KB Output is correct
27 Correct 4 ms 7772 KB Output is correct
28 Correct 5 ms 7756 KB Output is correct
29 Correct 5 ms 7652 KB Output is correct
30 Correct 4 ms 7516 KB Output is correct
31 Correct 5 ms 7728 KB Output is correct
32 Correct 5 ms 7512 KB Output is correct
33 Correct 4 ms 7516 KB Output is correct
34 Incorrect 112 ms 48512 KB Output isn't correct
35 Halted 0 ms 0 KB -