oj.uz

Submission #332287

# Submission time Handle Problem Language Result Execution time Memory
332287 2020-12-01T21:28:07 Z DanerZein Sjekira (COCI20_sjekira) C++14
50 / 110
 161 ms 20456 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--;
    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;
    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[j]=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:99:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |       for(int i=0;i<aux.size();i++){
      |                   ~^~~~~~~~~~~
sjekira.cpp:65:8: warning: unused variable 'sw' [-Wunused-variable]
   65 |   bool sw=0;
      |        ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 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 111 ms 16744 KB Output is correct
2 Correct 83 ms 12652 KB Output is correct
3 Correct 79 ms 12268 KB Output is correct
4 Correct 109 ms 14056 KB Output is correct
5 Correct 135 ms 20456 KB Output is correct
6 Correct 161 ms 20200 KB Output is correct
7 Correct 132 ms 17640 KB Output is correct
8 Correct 121 ms 16104 KB Output is correct
9 Correct 79 ms 10476 KB Output is correct
10 Correct 158 ms 20348 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 16 ms 492 KB Output is correct
7 Correct 10 ms 512 KB Output is correct
8 Correct 5 ms 492 KB Output is correct
9 Correct 13 ms 492 KB Output is correct
10 Correct 17 ms 492 KB Output is correct

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 111 ms 16744 KB Output is correct
7 Correct 83 ms 12652 KB Output is correct
8 Correct 79 ms 12268 KB Output is correct
9 Correct 109 ms 14056 KB Output is correct
10 Correct 135 ms 20456 KB Output is correct
11 Correct 161 ms 20200 KB Output is correct
12 Correct 132 ms 17640 KB Output is correct
13 Correct 121 ms 16104 KB Output is correct
14 Correct 79 ms 10476 KB Output is correct
15 Correct 158 ms 20348 KB Output is correct
16 Correct 16 ms 492 KB Output is correct
17 Correct 10 ms 512 KB Output is correct
18 Correct 5 ms 492 KB Output is correct
19 Correct 13 ms 492 KB Output is correct
20 Correct 17 ms 492 KB Output is correct
21 Incorrect 36 ms 4976 KB Output isn't correct
22 Halted 0 ms 0 KB -