Submission #1154013

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154013		i271828	Sjekira (COCI20_sjekira)	C++20	110 / 110	859 ms	27024 KiB

sjekira

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;

const int MAX=100005;

int N=5;
//vector<int> adj[MAX]={{1},{0,2},{1,3},{2,4},{3}};
vector<int> adj[MAX];
int A[MAX]={3,1,4,1,5};

bool vis[MAX];

int P[MAX];
set<int> C[MAX];
int root=-1;
/*
5
5 2 3 1 4
2 1
3 1
2 4
2 5
*/
void dfs_tree(int i,int p){
	int x=p;
	int prevx=-1;
	while (x!=-1&&A[x]<=A[i]) prevx=x, x=P[x];
	if (x==-1){
		if (root!=-1){
			C[i].insert(root);
			P[root]=i;
		}
		root=i;
		P[i]=-1;
	}else{
		P[i]=x;
		C[x].insert(i);
		if (prevx!=-1){
			C[x].erase(prevx);
			C[i].insert(prevx);
			P[prevx]=i;
		}
	}
	for (auto v:adj[i]){
		if (v==p) continue;
		dfs_tree(v,i);
	}
}

ll calc(int i){
	ll ans=0;
	vis[i]=true;
	
	for (auto x:C[i]){
		if (vis[x]) continue;
		ans+=A[i]+A[x];
		//cout<<i<<' '<<x<<'\n';
		auto y=calc(x);
		ans+=y;;
	}
	
	return ans;
}

int main(){
	//*
	cin>>N;
	for (int i=0;i<N;i++) cin>>A[i];
	for (int i=0;i<N-1;i++){
		int a,b;
		cin>>a>>b;
		a--,b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	/**/
	dfs_tree(0,-1);
	//for (int i=0;i<N;i++) cout<<i<<' '<<P[i]<<'\n';
	cout<<calc(root);
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 60 / 60