oj.uz

Submission #332283

# Submission time Handle Problem Language Result Execution time Memory
332283 2020-12-01T21:21:56 Z DanerZein Sjekira (COCI20_sjekira) C++14
10 / 110
 159 ms 20340 KB 
#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[100010];
bool ais[100010];
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);
  bool sw=0;
  for(ll i=0;i<n-1;i++){
    ll a,b;
    cin>>a>>b;
    a--; b--;
    if(a+1!=b) sw=1;
    cut[ii(a,b)]=0;
    cut[ii(b,a)]=0;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  if(sw){
    ll s=0;
    for(int i=0;i<n;i++) ais[i]=0;
    for(int i=0;i<n-1;i++){
      for(int j=0;j<n;j++) vis[i]=0;
      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

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 16744 KB Output is correct
2 Correct 81 ms 12652 KB Output is correct
3 Correct 78 ms 12140 KB Output is correct
4 Correct 90 ms 14056 KB Output is correct
5 Correct 134 ms 20340 KB Output is correct
6 Correct 159 ms 20328 KB Output is correct
7 Correct 132 ms 17640 KB Output is correct
8 Correct 125 ms 16104 KB Output is correct
9 Correct 77 ms 10476 KB Output is correct
10 Correct 148 ms 20200 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -