Submission #931528

#	Time	Username	Problem	Language	Result	Execution time	Memory
931528		pcc	Cat Exercise (JOI23_ho_t4)	C++14	41 / 100	120 ms	62036 KiB

Main

#include <bits/stdc++.h>
using namespace std;


#define int ll
#define ll long long
#define pii pair<int,int>
#define fs first
#define sc second

const int mxn = 2e5+10;
vector<int> op[mxn],tree[mxn];
vector<pii> ctree[mxn];
int N;
int arr[mxn],brr[mxn];

struct SEG{
	pii seg[mxn*4];
	void modify(int now,int l,int r,int p,int v){
		if(l == r){
			seg[now] = make_pair(v,l);
			return;
		}
		int mid = (l+r)>>1;
		if(mid>=p)modify(now*2+1,l,mid,p,v);
		else modify(now*2+2,mid+1,r,p,v);
		seg[now] = max(seg[now*2+1],seg[now*2+2]);
	}
	pii getbig(int now,int l,int r,int s,int e){
		if(l>=s&&e>=r)return seg[now];
		int mid = (l+r)>>1;
		if(mid>=e)return getbig(now*2+1,l,mid,s,e);
		else if(mid<s)return getbig(now*2+2,mid+1,r,s,e);
		else return max(getbig(now*2+1,l,mid,s,e),getbig(now*2+2,mid+1,r,s,e));
	}
	SEG(){
		memset(seg,0,sizeof(seg));
	}
};

SEG seg;
queue<int> q;

void cbuild(int now,int l,int r){
	if(now != l){
		int ls = seg.getbig(0,1,N,l,now-1).sc;
		ctree[now].push_back({ls,abs(ls-now)});
		cbuild(ls,l,now-1);
	}
	if(now != r){
		int rs = seg.getbig(0,1,N,now+1,r).sc;
		ctree[now].push_back({rs,abs(rs-now)});
		cbuild(rs,now+1,r);
	}
	return;
}

int dfs(int now){
	int dp = 0;
	for(auto nxt:ctree[now]){
		dp = max(dp,dfs(nxt.fs)+nxt.sc);
	}
	return dp;
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N;
	for(int i = 1;i<=N;i++)cin>>arr[i],brr[i] = i;
	for(int i = 1;i<N;i++){
		int a,b;
		cin>>a>>b;
		tree[a].push_back(b);
		tree[b].push_back(a);
	}
	for(int i = 1;i<=N;i++)seg.modify(0,1,N,i,arr[i]);
	int rt = seg.getbig(0,1,N,1,N).sc;
	cbuild(rt,1,N);
	cout<<dfs(rt);
}

Compilation message (stderr)

Main.cpp: In constructor 'SEG::SEG()':
Main.cpp:37:27: warning: 'void* memset(void*, int, size_t)' clearing an object of type 'struct std::pair<long long int, long long int>' with no trivial copy-assignment; use assignment instead [-Wclass-memaccess]
   37 |   memset(seg,0,sizeof(seg));
      |                           ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<long long int, long long int>' declared here
  211 |     struct pair
      |            ^~~~
Main.cpp: At global scope:
Main.cpp:66:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   66 | main(){
      | ^~~~

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