Submission #785458

#	Time	Username	Problem	Language	Result	Execution time	Memory
785458		KLPP	Cat Exercise (JOI23_ho_t4)	C++14	100 / 100	369 ms	49116 KiB

Main

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
typedef long long int lld;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
const int Mx=1000000;
int arr[Mx];
class DSU{
	public:
	int sz[Mx];
	int par[Mx];
	int cmp[Mx];

	void init(int n){
		rep(i,0,n)sz[i]=1,par[i]=i,cmp[i]=i;
	}
	int root(int x){
		if(par[x]==x)return x;
		par[x]=root(par[x]);
		return par[x];
	}
	void merge(int a, int b){
		a=root(a);
		b=root(b);
		if(a==b)return;
		if(sz[a]<sz[b])swap(a,b);
		sz[a]+=sz[b];
		par[b]=a;
		if(arr[cmp[a]]<arr[cmp[b]]){
			cmp[a]=cmp[b];
		}
	}
};
lld ans[Mx];
DSU D;
pair<int,int> p[Mx];


struct LCA {
  const int N, LOG;
  vector<int> depth;
  vector< vector<int> > dp;
  LCA(vector< vector<int> > &g) : N( (int)g.size() ), LOG( (int) log2(N)+1) {
    dp = vector< vector<int> > (N, vector<int> (LOG, -1) );
    depth = vector<int> (N, 0);
    dfs (g, 0);
    for (int j = 1; j < LOG; j++) {
      for (int i = 0; i < N; i++)
        if (dp[i][j - 1] != -1) dp[i][j] = dp[ dp[i][j - 1] ][j - 1];
    }
  }
  void dfs (vector< vector<int> > &g, int node, int p = -1) {
    dp[node][0] = p;
    for (auto to : g[node])
      if (to != p) { depth[to] = depth[node] + 1; dfs (g, to, node); }
  }
  // Edge weight = 1, otherwise change depth by sum till root
  int dist (int u, int v) { return depth[u] + depth[v] - 2 * depth[lca (u, v)]; }
  int kth (int u, int diff) {
    for (int i = LOG - 1; i >= 0; i--) if ((diff >> i) & 1) u = dp[u][i];
    return u;
  }
  int lca (int u, int v) {
    if (depth[u] < depth[v]) swap (u, v);
    u = kth (u, depth[u] - depth[v]);
    if (u == v) return u;
    for (int i = LOG - 1; i >= 0; i--)
      if (dp[u][i] != dp[v][i]) u = dp[u][i], v = dp[v][i];
    return dp[u][0];
  }
};

vector<vector<int> > nei;
void solve(){
	int n;
	cin>>n;
	rep(i,0,n)cin>>arr[i];
	rep(i,0,n)ans[i]=-100000000;
	D.init(n);
	nei.resize(n);
	rep(i,0,n-1){
		int x,y;
		cin>>x>>y;
		x--;y--;
		nei[x].push_back(y);
		nei[y].push_back(x);
	}
	LCA L(nei);
	rep(i,0,n)p[i]={arr[i],i};
	sort(p,p+n);
	lld fin=0;
	rep(i,0,n){
		int idx=p[i].second;
		ans[idx]=0;
		trav(a,nei[idx]){
			if(arr[a]<arr[idx]){
				int rep=D.cmp[D.root(a)];
				//cout<<idx<<" "<<rep<<" "<<L.dist(idx,rep)<<endl;
				ans[idx]=max(ans[idx],ans[rep]+L.dist(idx,rep));
			}
		}
		trav(a,nei[idx]){
			if(arr[a]<arr[idx]){
				D.merge(a,idx);
			}
		}
		fin=ans[idx];
	}
	cout<<fin<<"\n";
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tt=1;
	//cin>>tt;
	while(tt--){
		solve();
	}
}

• 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