Submission #1109436

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109436		Ludissey	Nile (IOI24_nile)	C++17	100 / 100	90 ms	21076 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>
#define int long long
#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> mnDEF;
vector<pair<int,pair<int,int>>> _a;
vector<int> mnEV;
vector<int> mnUV;
vector<pair<int,int>> mnBORDER;
vector<int> mn;
int 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]%2) sm-=mn[a];
  if(sz[b]%2) sm-=mn[b];
  if(sz[a]%2){
    mnEV[a]=min(mnEV[a], mnUV[b]);
    mnUV[a]=min(mnUV[a], mnEV[b]);
  }else{
    mnEV[a]=min(mnEV[a], mnEV[b]);
    mnUV[a]=min(mnUV[a], mnUV[b]);
  }
  mnBORDER[a].second=mnBORDER[b].second;
  sz[a]+=sz[b];
  mnDEF[a]=min(mnDEF[a],mnDEF[b]);
  mn[a]=min(mnDEF[a],min(mnEV[a],min(mnBORDER[a].first,mnBORDER[a].second)));
  if(sz[a]%2) sm+=mn[a];
}

void addMN(int x){
  int p=getParent(x);
  mnDEF[p]=min(mnDEF[p],(_a[x].second.first-_a[x].second.second));
  if(sz[p]%2) sm-=mn[p];
  mn[p]=min(mn[p],mnDEF[p]);
  if(sz[p]%2) sm+=mn[p];
}

std::vector<int> 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,1e17); sz.resize(n); parent.resize(n);
  mnDEF.resize(n,1e17);
  mnEV.resize(n,1e17);
  mnUV.resize(n,1e17);
  mnBORDER.resize(n,{1e17,1e17});
  vector<pair<int,int>> e(q);
  _a.resize(n);
  for (int i = 0; i < q; 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);
  vector<pair<int,int>> df2(n-2);
  for (int i = 0; i < n-1; i++) df[i]={_a[i+1].first-_a[i].first,i};
  for (int i = 0; i < n-2; i++) df2[i]={_a[i+2].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;
    mnEV[i]=_a[i].second.first-_a[i].second.second;
    mnBORDER[i]={_a[i].second.first-_a[i].second.second,_a[i].second.first-_a[i].second.second};
  }
  sort(all(df));
  sort(all(df2));
  std::vector<int> R(q, 0);
  int j=0;
  int j2=0;
  for (int i = 0; i < q; i++)
  {
    while(j<n-1){
      if(df[j].first>e[i].first) break;
      unite(df[j].second,df[j].second+1);
      j++;
    }
    while(j2<n-2){
      if(df2[j2].first>e[i].first) break;
      addMN(df2[j2].second+1);
      j2++;
    }
    R[e[i].second]=sm;
  }
  
  return R;
}

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