oj.uz

Submission #931528

# Submission time Handle Problem Language Result Execution time Memory
931528 2024-02-22T02:27:34 Z pcc Cat Exercise (JOI23_ho_t4) C++14
41 / 100
 120 ms 62036 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 30040 KB Output is correct
2 Correct 6 ms 30044 KB Output is correct
3 Correct 6 ms 30044 KB Output is correct
4 Correct 6 ms 30204 KB Output is correct
5 Correct 6 ms 30212 KB Output is correct
6 Correct 6 ms 30200 KB Output is correct
7 Correct 6 ms 30044 KB Output is correct
8 Correct 6 ms 30044 KB Output is correct
9 Correct 6 ms 30040 KB Output is correct
10 Correct 6 ms 30044 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 30040 KB Output is correct
2 Correct 6 ms 30044 KB Output is correct
3 Correct 6 ms 30044 KB Output is correct
4 Correct 6 ms 30204 KB Output is correct
5 Correct 6 ms 30212 KB Output is correct
6 Correct 6 ms 30200 KB Output is correct
7 Correct 6 ms 30044 KB Output is correct
8 Correct 6 ms 30044 KB Output is correct
9 Correct 6 ms 30040 KB Output is correct
10 Correct 6 ms 30044 KB Output is correct
11 Correct 6 ms 30296 KB Output is correct
12 Correct 6 ms 30044 KB Output is correct
13 Correct 6 ms 30204 KB Output is correct
14 Correct 6 ms 30044 KB Output is correct
15 Correct 6 ms 30044 KB Output is correct
16 Correct 6 ms 30296 KB Output is correct
17 Correct 6 ms 30044 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 30040 KB Output is correct
2 Correct 6 ms 30044 KB Output is correct
3 Correct 6 ms 30044 KB Output is correct
4 Correct 6 ms 30204 KB Output is correct
5 Correct 6 ms 30212 KB Output is correct
6 Correct 6 ms 30200 KB Output is correct
7 Correct 6 ms 30044 KB Output is correct
8 Correct 6 ms 30044 KB Output is correct
9 Correct 6 ms 30040 KB Output is correct
10 Correct 6 ms 30044 KB Output is correct
11 Correct 6 ms 30296 KB Output is correct
12 Correct 6 ms 30044 KB Output is correct
13 Correct 6 ms 30204 KB Output is correct
14 Correct 6 ms 30044 KB Output is correct
15 Correct 6 ms 30044 KB Output is correct
16 Correct 6 ms 30296 KB Output is correct
17 Correct 6 ms 30044 KB Output is correct
18 Correct 8 ms 30812 KB Output is correct
19 Correct 8 ms 30812 KB Output is correct
20 Correct 8 ms 30808 KB Output is correct
21 Correct 8 ms 30428 KB Output is correct
22 Correct 8 ms 30556 KB Output is correct
23 Correct 8 ms 30556 KB Output is correct
24 Correct 8 ms 30556 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 30040 KB Output is correct
2 Correct 6 ms 30044 KB Output is correct
3 Correct 6 ms 30044 KB Output is correct
4 Correct 6 ms 30204 KB Output is correct
5 Correct 6 ms 30212 KB Output is correct
6 Correct 6 ms 30200 KB Output is correct
7 Correct 6 ms 30044 KB Output is correct
8 Correct 6 ms 30044 KB Output is correct
9 Correct 6 ms 30040 KB Output is correct
10 Correct 6 ms 30044 KB Output is correct
11 Correct 6 ms 30296 KB Output is correct
12 Correct 6 ms 30044 KB Output is correct
13 Correct 6 ms 30204 KB Output is correct
14 Correct 6 ms 30044 KB Output is correct
15 Correct 6 ms 30044 KB Output is correct
16 Correct 6 ms 30296 KB Output is correct
17 Correct 6 ms 30044 KB Output is correct
18 Correct 8 ms 30812 KB Output is correct
19 Correct 8 ms 30812 KB Output is correct
20 Correct 8 ms 30808 KB Output is correct
21 Correct 8 ms 30428 KB Output is correct
22 Correct 8 ms 30556 KB Output is correct
23 Correct 8 ms 30556 KB Output is correct
24 Correct 8 ms 30556 KB Output is correct
25 Correct 6 ms 30044 KB Output is correct
26 Incorrect 8 ms 30428 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 30040 KB Output is correct
2 Correct 6 ms 30044 KB Output is correct
3 Correct 6 ms 30044 KB Output is correct
4 Correct 6 ms 30204 KB Output is correct
5 Correct 6 ms 30212 KB Output is correct
6 Correct 6 ms 30200 KB Output is correct
7 Correct 6 ms 30044 KB Output is correct
8 Correct 6 ms 30044 KB Output is correct
9 Correct 6 ms 30040 KB Output is correct
10 Correct 6 ms 30044 KB Output is correct
11 Correct 6 ms 30296 KB Output is correct
12 Correct 6 ms 30044 KB Output is correct
13 Correct 6 ms 30204 KB Output is correct
14 Correct 6 ms 30044 KB Output is correct
15 Correct 6 ms 30044 KB Output is correct
16 Correct 6 ms 30296 KB Output is correct
17 Correct 6 ms 30044 KB Output is correct
18 Correct 8 ms 30812 KB Output is correct
19 Correct 8 ms 30812 KB Output is correct
20 Correct 8 ms 30808 KB Output is correct
21 Correct 8 ms 30428 KB Output is correct
22 Correct 8 ms 30556 KB Output is correct
23 Correct 8 ms 30556 KB Output is correct
24 Correct 8 ms 30556 KB Output is correct
25 Correct 120 ms 62036 KB Output is correct
26 Correct 118 ms 60556 KB Output is correct
27 Correct 117 ms 60496 KB Output is correct
28 Correct 104 ms 45380 KB Output is correct
29 Correct 104 ms 45396 KB Output is correct
30 Correct 104 ms 45648 KB Output is correct
31 Correct 103 ms 45412 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 30044 KB Output is correct
2 Incorrect 6 ms 30300 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 30040 KB Output is correct
2 Correct 6 ms 30044 KB Output is correct
3 Correct 6 ms 30044 KB Output is correct
4 Correct 6 ms 30204 KB Output is correct
5 Correct 6 ms 30212 KB Output is correct
6 Correct 6 ms 30200 KB Output is correct
7 Correct 6 ms 30044 KB Output is correct
8 Correct 6 ms 30044 KB Output is correct
9 Correct 6 ms 30040 KB Output is correct
10 Correct 6 ms 30044 KB Output is correct
11 Correct 6 ms 30296 KB Output is correct
12 Correct 6 ms 30044 KB Output is correct
13 Correct 6 ms 30204 KB Output is correct
14 Correct 6 ms 30044 KB Output is correct
15 Correct 6 ms 30044 KB Output is correct
16 Correct 6 ms 30296 KB Output is correct
17 Correct 6 ms 30044 KB Output is correct
18 Correct 8 ms 30812 KB Output is correct
19 Correct 8 ms 30812 KB Output is correct
20 Correct 8 ms 30808 KB Output is correct
21 Correct 8 ms 30428 KB Output is correct
22 Correct 8 ms 30556 KB Output is correct
23 Correct 8 ms 30556 KB Output is correct
24 Correct 8 ms 30556 KB Output is correct
25 Correct 6 ms 30044 KB Output is correct
26 Incorrect 8 ms 30428 KB Output isn't correct
27 Halted 0 ms 0 KB -