Submission #332282

#	Time	Username	Problem	Language	Result	Execution time	Memory
332282		DanerZein	Sjekira (COCI20_sjekira)	C++14	50 / 110	158 ms	20348 KiB

sjekira

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
vector<ll> x;
vector<vi> G;
int tree[400010];
void init(int node,int a,int b){
  if(a>b) return;
  if(a==b){
    tree[node]=a;
    return;
  }
  int mid=(a+b)/2;
  init(2*node+1,a,mid);
  init(2*node+2,mid+1,b);
  if(x[tree[2*node+1]]>x[tree[2*node+2]])
    tree[node]=tree[2*node+1];
  else
    tree[node]=tree[2*node+2];	    
}
int query(int node,int a,int b,int l,int r){
  if(b<l or a>r) {
    return -1;
  }
  if(l<=a and r>=b) return tree[node];
  int mid=(a+b)/2;
  int lc=query(2*node+1,a,mid,l,r);
  int rc=query(2*node+2,mid+1,b,l,r);
  int vl,vr;
  vl=vr=-1;
  if(rc!=-1) vr=x[rc];
  if(lc!=-1) vl=x[lc];
  if(vl>vr){
    return lc;
  }
  else return rc;
}
bool vis[1010];
bool ais[1010];
map<ii,int> cut;
int dfs(int u){
  vis[u]=1;
  int ans=x[u];
  for(auto &v:G[u]){
    if(!vis[v] && !cut[ii(u,v)]){
      ans=max(ans,dfs(v));
    }
  }
  return ans;
}
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ll n;
  cin>>n;
  vector<ii> con;
  for(ll i=0;i<n;i++){
    ll a; cin>>a;
    x.push_back(a);
  }
  G.resize(n);
  for(ll i=0;i<n-1;i++){
    ll a,b;
    cin>>a>>b;
    a--; b--;
    cut[ii(a,b)]=0;
    cut[ii(b,a)]=0;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  if(n<=1000){
    ll s=0;
    memset(ais,0,sizeof ais);
    for(int i=0;i<n-1;i++){
      memset(vis,0,sizeof vis);
      int id=-1,ma=-1;
      for(int j=0;j<n;j++){
	if(!ais[j] && ma<x[j]){
	  ma=x[j];
	  id=j;
	}
      }
      if(id==-1) break;
      vector<int> aux;
      for(auto &v:G[id]){
	//cout<<v<<" ";
	if(!cut[ii(id,v)]){
	  cut[ii(id,v)]=1;
	  cut[ii(v,id)]=1;
	  aux.push_back(dfs(v));
	}
      }
      // cout<<endl;
      //cout<<i<<": "<<id<<" "<<ma<<endl;
      for(int i=0;i<aux.size();i++){
	//cout<<aux[i]<<" ";
	s+=(ma+aux[i]);
      }
      // cout<<endl;
      ais[id]=1;
    }
    cout<<s<<endl;
  }
  else{
    int l=0,r=n-1;
    queue<ii> q;
    q.push(ii(l,r));
    init(0,0,n-1);
    ll s=0;
    while(!q.empty()){
      l=q.front().first;
      r=q.front().second;
      q.pop();
      int id=query(0,0,n-1,l,r);
      if(id!=l){
	int ml=query(0,0,n-1,l,id-1);
	s+=(x[ml]+x[id]);
	if(l!=id-1){
	  q.push(ii(l,id-1));
	}
      }
      if(id!=r){
	int ml=query(0,0,n-1,id+1,r);
	s+=(x[ml]+x[id]);
	if(r!=id+1){
	  q.push(ii(id+1,r));
	}
      }
    }
    cout<<s<<endl;
  }
}

Compilation message (stderr)

sjekira.cpp: In function 'int main()':
sjekira.cpp:98:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |       for(int i=0;i<aux.size();i++){
      |                   ~^~~~~~~~~~~

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