제출 #827890

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
827890		CSQ31	Cat Exercise (JOI23_ho_t4)	C++17	54 / 100	195 ms	62612 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],n;
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];
}

////lca template
int t[4*MAXN];
void upd(int v,int pos,int tl,int tr,int val){
	if(tl==tr){
		t[v] = val;
		return;
	}
	int tm = (tl+tr)/2;
	if(pos<=tm)upd(2*v,pos,tl,tm,val);
	else upd(2*v+1,pos,tm+1,tr,val);
	t[v] = max(t[2*v],t[2*v+1]);
}
int query(int v,int l,int r,int tl,int tr){
	if(l>r)return -1;
	if(l==tl && r==tr)return t[v];
	int tm = (tl+tr)/2;
	return max(
	query(2*v,l,min(r,tm),tl,tm),
	query(2*v+1,max(l,tm+1),r,tm+1,tr));
}
int ded[MAXN];
int solve(int v){
	int rt = query(1,tin[v],tout[v],1,n);
	//cout<<v<<" "<<rt<<'\n';
	rt = rp[rt];
	ded[rt] = 1;
	upd(1,tin[rt],1,n,-1);
	for(int x:adj[rt]){
		if(x == par[0][rt] || ded[x])continue;
		int y = solve(x);
		g[rt].pb(y);
	}
	if(rt != v){
		int y = solve(v);
		g[rt].pb(y);
	}
	return rt;
}
int dfs2(int v){
	int mx = 0;
	for(int x:g[v]){
		mx = max(mx,dfs2(x) + dist(x,v));
	}
	return mx;
}
//segtree
int main()
{
	owo
	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);
	for(int i=1;i<=n;i++)upd(1,tin[i],1,n,p[i]);
	
	solve(rp[n]);
	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: 23 / 23
• Subtask 7: 0 / 26