oj.uz

Submission #931551

# Submission time Handle Problem Language Result Execution time Memory
931551 2024-02-22T04:01:41 Z pcc Cat Exercise (JOI23_ho_t4) C++14
14 / 100
 134 ms 77612 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
#define pll pii

const int mxn = 2e5+10;
vector<int> tree[mxn];
vector<pii> ctree[mxn];
int N;
int arr[mxn];
const int SS = 5e5;
int SSS;

vector<int> dfn;
pii eul[mxn];

struct SEG{
	struct node{
		pii mx;
		int tag;
		node(){
			mx.fs = mx.sc = tag = 0;
		}
	};
	node seg[mxn*4];
	SEG(){
		for(auto &i:seg)i.mx.fs = i.mx.sc = i.tag = 0;
	}
	void push(int now){
		seg[now].mx.fs += seg[now].tag;
		if(now*2+2>=mxn*4)exit(0);
		seg[now*2+1].tag += seg[now].tag;
		seg[now*2+2].tag += seg[now].tag;
		return;
	}
	node pull(node ls,node rs){
		node re;
		ls.mx.fs += ls.tag,rs.mx.fs += rs.tag;
		re.mx = max(ls.mx,rs.mx);
		return re;
	}
	void modify(int now,int l,int r,int s,int e,int v){
		if(e<s)exit(0);
		if(l>=s&&e>=r){
			if(l == r)seg[now].mx.sc = l;
			seg[now].tag += v;
			return;
		}
		push(now);
		int mid = (l+r)>>1;
		if(mid>=s)modify(now*2+1,l,mid,s,e,v);
		if(mid<e)modify(now*2+2,mid+1,r,s,e,v);
		seg[now] = pull(seg[now*2+1],seg[now*2+2]);
		return;
	}
	pll getbig(int now,int l,int r,int s,int e){
		if(l>=s&&e>=r)return make_pair(seg[now].mx.fs+seg[now].tag,seg[now].mx.sc);
		if(l==r)exit(0);
		push(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 seg;

namespace DB{
	int par[mxn][20];
	int dep[mxn];
	void dfs(int now){
		for(int i = 1;i<20;i++)par[now][i] = par[par[now][i-1]][i-1];
		for(auto nxt:tree[now]){
			if(nxt == par[now][0])continue;
			dep[nxt] = dep[now]+1;
			par[nxt][0] = now;
			dfs(nxt);
		}
		return;
	}
	void GO(int rt){
		par[rt][0] = rt;
		dfs(rt);
	}
	int lca(int a,int b){
		if(dep[a]<dep[b])swap(a,b);
		int d = dep[a]-dep[b];
		for(int i = 19;i>=0;i--){
			if(d&(1<<i))a = par[a][i];
		}
		for(int i = 19;i>=0;i--){
			if(par[a][i] != par[b][i])a = par[a][i],b = par[b][i];
		}
		return a==b?a:par[a][0];
	}
	int up(int a,int d){
		for(int i = 19;i>=0;i--){
			if(d&(1<<i))a = par[a][i];
		}
		return a;
	}
	int dist(int a,int b){
		return dep[a]+dep[b]-dep[lca(a,b)]*2;
	}
}

namespace CTREE{
	void add_edge(int a,int b,int c){
		ctree[a].push_back(make_pair(b,c));
		//cerr<<"edge:"<<a<<','<<b<<":"<<c<<endl;
	}
	void GO(int rt,int par){
		assert(rt != par);
		for(auto nxt:tree[rt]){
			if(nxt == DB::par[rt][0])continue;
			//cerr<<rt<<":"<<nxt<<":";
			nxt = seg.getbig(0,1,N,eul[nxt].fs,eul[nxt].sc).sc;
			nxt = dfn[nxt];
			//cerr<<rt<<":"<<nxt<<endl;assert(rt != nxt);
			if(seg.getbig(0,1,N,eul[nxt].fs,eul[nxt].sc).fs > 0)add_edge(rt,nxt,DB::dist(rt,nxt));
			GO(nxt,rt);
		}
		seg.modify(0,1,N,eul[rt].fs,eul[rt].sc,-mxn);
		int u = DB::up(rt,DB::dep[rt]-DB::dep[par]-1);
		auto nx = seg.getbig(0,1,N,eul[u].fs,eul[u].sc);
		if(nx.fs<=0)return;
		nx.sc = dfn[nx.sc];
		//cerr<<"UP:"<<rt<<":"<<nx.fs<<','<<nx.sc<<endl;
		assert(nx.sc != rt);
		add_edge(rt,nx.sc,DB::dist(rt,nx.sc));
		GO(nx.sc,par);
		return;
	}
}


void edfs(int now,int par){
	SSS++;
	if(SSS>=SS)exit(0);
	dfn.push_back(now);
	eul[now].fs = dfn.size()-1;
	for(auto nxt:tree[now]){
		if(nxt == par)continue;
		edfs(nxt,now);
	}
	eul[now].sc = dfn.size()-1;
	SSS--;
	return;
}
namespace DP{
	int dp[mxn];
	void dfs(int now,int par){
		dp[now] = 0;
		for(auto nxt:ctree[now]){
			if(nxt.fs == par)continue;
			dfs(nxt.fs,now);
			dp[now] = max(dp[now],dp[nxt.fs]+nxt.sc);
		}
		return;
	}
	void GO(int rt){
		dfs(rt,rt);
	}
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N;
	for(int i = 1;i<=N;i++)cin>>arr[i];
	for(int i = 1;i<N;i++){
		int a,b;
		cin>>a>>b;
		tree[a].push_back(b);
		tree[b].push_back(a);
	}
	dfn.push_back(0);
	int rt = max_element(arr+1,arr+N+1)-arr;
	DB::GO(rt);
	edfs(rt,rt);//get euler
	//for(int i = 1;i<=N;i++)cerr<<dfn[i]<<',';cerr<<endl;
	//for(int i = 1;i<=N;i++)cerr<<i<<"::"<<eul[i].fs<<','<<eul[i].sc<<endl;
	for(int i = 1;i<=N;i++)seg.modify(0,1,N,i,i,arr[dfn[i]]);
	if(N>300)exit(0);
	CTREE::GO(rt,0);
	DP::GO(rt);
	cout<<DP::dp[rt];
}

Compilation message

Main.cpp:174:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  174 | main(){
      | ^~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 34652 KB Output is correct
2 Correct 9 ms 34652 KB Output is correct
3 Correct 8 ms 34652 KB Output is correct
4 Correct 8 ms 34652 KB Output is correct
5 Correct 7 ms 34652 KB Output is correct
6 Correct 8 ms 34696 KB Output is correct
7 Correct 8 ms 34648 KB Output is correct
8 Correct 8 ms 34652 KB Output is correct
9 Correct 7 ms 34648 KB Output is correct
10 Correct 7 ms 34652 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 34652 KB Output is correct
2 Correct 9 ms 34652 KB Output is correct
3 Correct 8 ms 34652 KB Output is correct
4 Correct 8 ms 34652 KB Output is correct
5 Correct 7 ms 34652 KB Output is correct
6 Correct 8 ms 34696 KB Output is correct
7 Correct 8 ms 34648 KB Output is correct
8 Correct 8 ms 34652 KB Output is correct
9 Correct 7 ms 34648 KB Output is correct
10 Correct 7 ms 34652 KB Output is correct
11 Correct 9 ms 34652 KB Output is correct
12 Correct 10 ms 34712 KB Output is correct
13 Correct 9 ms 34652 KB Output is correct
14 Correct 8 ms 34652 KB Output is correct
15 Correct 8 ms 34652 KB Output is correct
16 Correct 9 ms 34652 KB Output is correct
17 Correct 9 ms 34652 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 34652 KB Output is correct
2 Correct 9 ms 34652 KB Output is correct
3 Correct 8 ms 34652 KB Output is correct
4 Correct 8 ms 34652 KB Output is correct
5 Correct 7 ms 34652 KB Output is correct
6 Correct 8 ms 34696 KB Output is correct
7 Correct 8 ms 34648 KB Output is correct
8 Correct 8 ms 34652 KB Output is correct
9 Correct 7 ms 34648 KB Output is correct
10 Correct 7 ms 34652 KB Output is correct
11 Correct 9 ms 34652 KB Output is correct
12 Correct 10 ms 34712 KB Output is correct
13 Correct 9 ms 34652 KB Output is correct
14 Correct 8 ms 34652 KB Output is correct
15 Correct 8 ms 34652 KB Output is correct
16 Correct 9 ms 34652 KB Output is correct
17 Correct 9 ms 34652 KB Output is correct
18 Incorrect 10 ms 35160 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 34652 KB Output is correct
2 Correct 9 ms 34652 KB Output is correct
3 Correct 8 ms 34652 KB Output is correct
4 Correct 8 ms 34652 KB Output is correct
5 Correct 7 ms 34652 KB Output is correct
6 Correct 8 ms 34696 KB Output is correct
7 Correct 8 ms 34648 KB Output is correct
8 Correct 8 ms 34652 KB Output is correct
9 Correct 7 ms 34648 KB Output is correct
10 Correct 7 ms 34652 KB Output is correct
11 Correct 9 ms 34652 KB Output is correct
12 Correct 10 ms 34712 KB Output is correct
13 Correct 9 ms 34652 KB Output is correct
14 Correct 8 ms 34652 KB Output is correct
15 Correct 8 ms 34652 KB Output is correct
16 Correct 9 ms 34652 KB Output is correct
17 Correct 9 ms 34652 KB Output is correct
18 Incorrect 10 ms 35160 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 34652 KB Output is correct
2 Correct 9 ms 34652 KB Output is correct
3 Correct 8 ms 34652 KB Output is correct
4 Correct 8 ms 34652 KB Output is correct
5 Correct 7 ms 34652 KB Output is correct
6 Correct 8 ms 34696 KB Output is correct
7 Correct 8 ms 34648 KB Output is correct
8 Correct 8 ms 34652 KB Output is correct
9 Correct 7 ms 34648 KB Output is correct
10 Correct 7 ms 34652 KB Output is correct
11 Correct 9 ms 34652 KB Output is correct
12 Correct 10 ms 34712 KB Output is correct
13 Correct 9 ms 34652 KB Output is correct
14 Correct 8 ms 34652 KB Output is correct
15 Correct 8 ms 34652 KB Output is correct
16 Correct 9 ms 34652 KB Output is correct
17 Correct 9 ms 34652 KB Output is correct
18 Incorrect 10 ms 35160 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 34652 KB Output is correct
2 Correct 8 ms 34792 KB Output is correct
3 Incorrect 134 ms 77612 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 34652 KB Output is correct
2 Correct 9 ms 34652 KB Output is correct
3 Correct 8 ms 34652 KB Output is correct
4 Correct 8 ms 34652 KB Output is correct
5 Correct 7 ms 34652 KB Output is correct
6 Correct 8 ms 34696 KB Output is correct
7 Correct 8 ms 34648 KB Output is correct
8 Correct 8 ms 34652 KB Output is correct
9 Correct 7 ms 34648 KB Output is correct
10 Correct 7 ms 34652 KB Output is correct
11 Correct 9 ms 34652 KB Output is correct
12 Correct 10 ms 34712 KB Output is correct
13 Correct 9 ms 34652 KB Output is correct
14 Correct 8 ms 34652 KB Output is correct
15 Correct 8 ms 34652 KB Output is correct
16 Correct 9 ms 34652 KB Output is correct
17 Correct 9 ms 34652 KB Output is correct
18 Incorrect 10 ms 35160 KB Output isn't correct
19 Halted 0 ms 0 KB -