Submission #332264

#	Time	Username	Problem	Language	Result	Execution time	Memory
332264		DanerZein	Sjekira (COCI20_sjekira)	C++14	20 / 110	131 ms	4584 KiB

sjekira

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
vector<ll> x,per;
vector<ii> y;
ll pa[20],ma[20];
const ll MAX=1e18;
void init(ll n){
  for(ll i=0;i<n;i++){
    pa[i]=i;
    ma[i]=x[i];
  }
}
ll findset(ll i){
  if(pa[i]==i)return i;
  return pa[i]=findset(pa[i]);
}
bool issameset(ll i,ll j){
  return findset(i)==findset(j);
}
void unionset(ll i,ll j){
  if(!issameset(i,j)){
    ll u=findset(i),v=findset(j);
    pa[u]=v;
    ma[v]=max(ma[u],ma[v]);
  }
}
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;
}
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ll n;
  cin>>n;
  vector<ii> con;
  map<ll,ii>no;
  for(ll i=0;i<n;i++){
    ll a; cin>>a;
    x.push_back(a);
  }
  for(ll i=0;i<n-1;i++){
    ll a,b;
    cin>>a>>b;
    a--; b--;
    if(n<=10){
      no[i]=ii(a,b);
      per.push_back(i);
      con.push_back(ii(a,b));
    }
  }
  if(n<=10){
    ll mi=MAX;
    do{
      init(n);
      ll s=0;
      for(ll i=0;i<n-1;i++){
	ll id=per[i];
	ll u=no[id].first,v=no[id].second;
	s+=(ma[findset(u)]+ma[findset(v)]);
	unionset(u,v);
      }
      mi=min(mi,s);
    }while(next_permutation(per.begin(),per.end()));
    cout<<mi<<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;
  }
}

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