Submission #850627

#	Time	Username	Problem	Language	Result	Execution time	Memory
850627		StefanSebez	Cat Exercise (JOI23_ho_t4)	C++14	51 / 100	2081 ms	45712 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
const int N=2*1e5+50;
map<pair<int,int>,int>mapa;
vector<int>E[N];
ll dp[N];
bool was[N];
pair<int,int> DFS(int u,int par,int depth)
{
	pair<int,int> x=make_pair(u,depth);
	for(auto i:E[u])
	{
		if(was[i] && i!=par)
		{
			pair<int,int>y=DFS(i,u,depth+1);
			if(x.fi<y.fi) x=y;
		}
	}
	return x;
}
int main()
{
    int n;scanf("%i",&n);
    int a[n+1],L[n+1],R[n+1];
    vector<int>mono;
    for(int i=1;i<=n;i++)
	{
		L[i]=0,R[i]=n+1;
		scanf("%i",&a[i]);
		while(!mono.empty() && a[mono.back()]<a[i])
		{
			R[mono.back()]=i;
			mono.pop_back();
		}
		if(!mono.empty()) L[i]=mono.back();
		mono.push_back(i);
	}
	pair<int,int>par[n+1];
	for(int i=1;i<=n;i++)
	{
		mapa[{L[i],R[i]}]=i;
		par[i]=make_pair(R[i]-L[i],i);
	}
	sort(par+1,par+n+1);
	for(int i=1;i<=n;i++)
	{
		int j=par[i].se,maks=0,l=mapa[{L[j],j}],r=mapa[{j,R[j]}];
		if(j-L[j]>1)dp[j]=max(dp[l]+j-l,dp[j]);
		if(R[j]-j>1)dp[j]=max(dp[r]+r-j,dp[j]);
	}
	bool bul=true;
    for(int i=1;i<n;i++)
	{
		int u,v;
		scanf("%i%i",&u,&v);
		E[a[u]].push_back(a[v]);
		E[a[v]].push_back(a[u]);
		if(!(u==i && v==i+1))bul=false;
	}
	if(bul) {printf("%lld\n",dp[mapa[{0,n+1}]]);return 0;}
	for(int i=1;i<=n;i++)
	{
		dp[i]=0;
		for(auto u:E[i])
		{
			if(was[u])
			{
				pair<int,int> x=DFS(u,i,1);
				dp[i]=max(dp[x.fi]+x.se,dp[i]);
				//printf("%i %i: %i %i\n",u,i,x.fi,x.se);
			}
		}
		was[i]=true;
		//printf("%i: %lld\n",i,dp[i]);
	}
	printf("%lld\n",dp[n]);
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:50:19: warning: unused variable 'maks' [-Wunused-variable]
   50 |   int j=par[i].se,maks=0,l=mapa[{L[j],j}],r=mapa[{j,R[j]}];
      |                   ^~~~
Main.cpp:26:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     int n;scanf("%i",&n);
      |           ~~~~~^~~~~~~~~
Main.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |   scanf("%i",&a[i]);
      |   ~~~~~^~~~~~~~~~~~
Main.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |   scanf("%i%i",&u,&v);
      |   ~~~~~^~~~~~~~~~~~~~

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