Submission #827881

#	Time	Username	Problem	Language	Result	Execution time	Memory
827881		CSQ31	Cat Exercise (JOI23_ho_t4)	C++17	31 / 100	2087 ms	50424 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
const int MAXN = 2e5+5;
vector<int>adj[MAXN],g[MAXN];
int p[MAXN],rp[MAXN],t[4*MAXN],lazy[4*MAXN];
int tin[MAXN],tout[MAXN],dep[MAXN],par[20][MAXN];
int timer = 0;
void dfs(int v,int u){
	tin[v] = ++timer;
	for(int x:adj[v]){
	    if(x == u)continue;	
	    par[0][x] = v;
	    dep[x] = dep[v]+1;
	    for(int i=1;i<=18;i++){
			par[i][x] = par[i-1][par[i-1][x]];
		}
		dfs(x,v);
	}
	tout[v] = timer;
}
bool ancestor(int v,int u){return(tin[v] >= tin[u] && tout[u] >= tout[v]);}//is u an ancestor of v?
int lca(int v,int u){
	if(dep[v] > dep[u])swap(u,v);
	int dist = dep[u]-dep[v];
	for(int i=0;dist;i++,dist>>=1){
		if(dist&1)u = par[i][u];
	}
	if(u == v)return u;
	for(int i=18;i>=0;i--){
		if(par[i][v] != par[i][u]){
			u = par[i][u];
			v = par[i][v];
		}
	}
	return par[0][v];
}
int dist(int u,int v){
	int w = lca(u,v);
	return dep[u] + dep[v] - 2*dep[w];
}

int dfs2(int v){
	int mx = 0;
	for(int x:g[v]){
		mx = max(mx,dfs2(x) + dist(x,v));
	}
	return mx;
}
int ded[MAXN];
int find(int v,int u){
	int res = p[v];
	for(int x:adj[v]){
		if(x==u || ded[x])continue;
		res = max(res,find(x,v));
	}
	return res;
}
void solve(int v,int p){
	v = rp[find(v,-1)];
	ded[v] = 1;
	if(p)g[p].pb(v);
	for(int x:adj[v]){
		if(ded[x])continue;
		solve(x,v);
	}
}

int main()
{
	owo
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>p[i];
		rp[p[i]] = i;
	}
	for(int i=1;i<n;i++){
		int v,u;
		cin>>v>>u;
		adj[v].pb(u);
		adj[u].pb(v);
	}
	dfs(rp[n],-1);
	solve(1,0);
	cout<<dfs2(rp[n]);
	
	
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 10 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 23
• Subtask 7: 0 / 26