Submission #1067094

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067094		Dennis_Jason	Cat Exercise (JOI23_ho_t4)	C++14	100 / 100	266 ms	71504 KiB

Main

#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 (stderr)

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 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 23 / 23
• Subtask 7: 26 / 26