Submission #1109378

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109378		Ludissey	Nile (IOI24_nile)	C++17	0 / 100	28 ms	10104 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
 
using namespace std;

vector<int> parent;
vector<int> sz;
vector<int> mn;
long long sm=0;

int getParent(int x){
  if(parent[x]==x) return x;
  return parent[x]=getParent(parent[x]);
}

void unite(int a, int b){
  a=getParent(a); b=getParent(b);
  if(a==b) return;
  parent[b]=a;
  if(sz[a]<sz[b]) swap(a,b);
  if(sz[a]%2) sm-=mn[a];
  if(sz[b]%2) sm-=mn[b];
  sz[a]+=sz[b];
  mn[a]=min(mn[a],mn[b]);
  if(sz[a]%2) sm+=mn[a];
}

std::vector<long long> calculate_costs(std::vector<signed> W, std::vector<signed> A,  std::vector<signed> B, std::vector<signed> E) {
  int q = sz(E);
  int n=sz(W);
  mn.resize(n); sz.resize(n); parent.resize(n);
  vector<pair<int,int>> e(q);
  vector<pair<int,pair<int,int>>> a(n);
  for (int i = 0; i < n; i++) e[i]={E[i],i};
  for (int i = 0; i < n; i++) a[i]={W[i],{A[i],B[i]}};
  sort(all(a));
  sort(all(e));
  vector<pair<int,int>> df(n-1);
  for (int i = 0; i < n-1; i++) df[i]={a[i+1].first-a[i].first,i};
  sm=0;
  for (int i = 0; i < n; i++)
  {
    sm+=a[i].second.first;
    sz[i]=1;
    parent[i]=i;
    mn[i]=a[i].second.first-a[i].second.second;
  }
  sort(all(df));
  std::vector<long long> R(q, 0);
  int j=0;
  for (int i = 0; i < n; i++)
  {
    while(j<n-1){
      if(df[j].first>e[i].first) break;
      unite(df[j].second,df[i].second+1);
      j++;
    }
    R[e[i].second]=sm;
  }
  
  return R;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 6
• Subtask 2: 0 / 13
• Subtask 3: 0 / 17
• Subtask 4: 0 / 11
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15
• Subtask 7: 0 / 18