oj.uz

Submission #332282

# Submission time Handle Problem Language Result Execution time Memory
332282 2020-12-01T21:19:38 Z DanerZein Sjekira (COCI20_sjekira) C++14
50 / 110
 158 ms 20348 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[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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 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 0 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 82 ms 12544 KB Output is correct
3 Correct 81 ms 12396 KB Output is correct
4 Correct 93 ms 14056 KB Output is correct
5 Correct 134 ms 20348 KB Output is correct
6 Correct 158 ms 20072 KB Output is correct
7 Correct 132 ms 17640 KB Output is correct
8 Correct 125 ms 16104 KB Output is correct
9 Correct 79 ms 10584 KB Output is correct
10 Correct 147 ms 20328 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 0 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 0 ms 364 KB Output is correct
6 Correct 11 ms 492 KB Output is correct
7 Correct 10 ms 492 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 0 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 0 ms 364 KB Output is correct
6 Correct 111 ms 16744 KB Output is correct
7 Correct 82 ms 12544 KB Output is correct
8 Correct 81 ms 12396 KB Output is correct
9 Correct 93 ms 14056 KB Output is correct
10 Correct 134 ms 20348 KB Output is correct
11 Correct 158 ms 20072 KB Output is correct
12 Correct 132 ms 17640 KB Output is correct
13 Correct 125 ms 16104 KB Output is correct
14 Correct 79 ms 10584 KB Output is correct
15 Correct 147 ms 20328 KB Output is correct
16 Correct 11 ms 492 KB Output is correct
17 Correct 10 ms 492 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 34 ms 5488 KB Output isn't correct
22 Halted 0 ms 0 KB -