oj.uz

Submission #332264

# Submission time Handle Problem Language Result Execution time Memory
332264 2020-12-01T19:55:48 Z DanerZein Sjekira (COCI20_sjekira) C++14
20 / 110
 131 ms 4584 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 131 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 2152 KB Output is correct
2 Correct 47 ms 2752 KB Output is correct
3 Correct 47 ms 2668 KB Output is correct
4 Correct 52 ms 3432 KB Output is correct
5 Correct 78 ms 4376 KB Output is correct
6 Correct 101 ms 4584 KB Output is correct
7 Correct 83 ms 3944 KB Output is correct
8 Correct 83 ms 3816 KB Output is correct
9 Correct 49 ms 2412 KB Output is correct
10 Correct 92 ms 4456 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 131 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Incorrect 1 ms 364 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 131 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 61 ms 2152 KB Output is correct
7 Correct 47 ms 2752 KB Output is correct
8 Correct 47 ms 2668 KB Output is correct
9 Correct 52 ms 3432 KB Output is correct
10 Correct 78 ms 4376 KB Output is correct
11 Correct 101 ms 4584 KB Output is correct
12 Correct 83 ms 3944 KB Output is correct
13 Correct 83 ms 3816 KB Output is correct
14 Correct 49 ms 2412 KB Output is correct
15 Correct 92 ms 4456 KB Output is correct
16 Incorrect 1 ms 364 KB Output isn't correct
17 Halted 0 ms 0 KB -