Submission #1106495

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106495		Noname_1900	Nile (IOI24_nile)	C++17	51 / 100	86 ms	19140 KiB

nile

#include "nile.h"
using namespace std;
#include<bits/stdc++.h>
const int Nmin = 100000;
#define int long long
const int INFINI = 1000000000000;
struct T {
  int normal, enPair;
  T()
  {
    normal = 0;
    enPair = 0;
  }
  bool operator<(const T &other) const {
    if(normal != other.normal)
      return normal < other.normal;
    else
      return enPair > other.enPair;
  }
  T(int a, int b)
  {
    normal = a;
    enPair = b;
  }
};
bool existe[Nmin][2];
vector<pair<int, pair<int, int>>> aretes;
int boss[Nmin];

int minRouge[Nmin], minNoir[Nmin];
pair<int, T> infos[Nmin];//W, A, B
int sommeB[Nmin];
int sommeTotal;
int taille[Nmin];
int sommeComposante[Nmin];

int findBoss(int noeud)
{
  if(boss[noeud] == noeud)
  {
    return noeud;
  }
  return boss[noeud] = findBoss(boss[noeud]);
}
void comparerBalance(int noeud)
{
      minRouge[findBoss(noeud)] = min(minRouge[findBoss(noeud)], (infos[noeud].second.normal-infos[noeud].second.enPair));
      minNoir[findBoss(noeud)] = min(minNoir[findBoss(noeud)], (infos[noeud].second.normal-infos[noeud].second.enPair));
    
}
void faire(int bossA, int bossB, bool inverserCouleur)
{
  if(inverserCouleur)
  {
    minRouge[bossA] = min(minRouge[bossA], minNoir[bossB]);
    minNoir[bossA] = min(minNoir[bossA], minRouge[bossB]);
  }
  else
  {
    minRouge[bossA] = min(minRouge[bossA], minRouge[bossB]);
    minNoir[bossA] = min(minNoir[bossA], minNoir[bossB]);
  }
}
void merge(int a, int b)
{
  //cout << "hdjlkhskj" << endl;
  int bossA = findBoss(a), bossB = findBoss(b);
 // cout << bossA << " " << bossB << endl;
  if(bossA == bossB)
  {
      int balance = a+1;
      comparerBalance(balance);
      sommeTotal -= sommeComposante[bossA];
  }
  else
  {
     // cout << "kjhdkjhdkjhskjhdskjhsdjskhkdjsh" << endl;
      bool debutB = bossB%2;
      int debutA = bossA%2;
      int finA = (debutA + taille[bossA]-1)%2;
      if(finA == debutB)
        faire(bossA, bossB, 1);
      else
      {
        faire(bossA, bossB, 0);
      }
      sommeB[bossA] += sommeB[bossB];
     // cout << taille[bossA] << " " << taille[bossB] << endl;
      taille[bossA] += taille[bossB];
     // cout << taille[bossA] << endl;
      sommeTotal -= sommeComposante[bossA] + sommeComposante[bossB];
      boss[bossB] = bossA;
     // cout << boss[2] << endl;

      
  }
  int noeud = bossA;
 // cout << sommeTotal << endl;
  if(taille[noeud]%2 == 0)
  {
   // cout << "pair <" << endl;
    sommeComposante[noeud] = sommeB[noeud];
    sommeTotal += sommeComposante[noeud];
   // cout << sommeTotal << endl;
    //cout << "fin" << endl;
    return;
  }
  if(bossA%2 == 0)
  {
    sommeComposante[noeud] = sommeB[noeud]+minRouge[noeud];
    sommeTotal += sommeB[noeud]+minRouge[noeud];
  }
  else
  {
    sommeComposante[noeud] = sommeB[noeud]+minNoir[noeud];
      sommeTotal += sommeB[noeud]+minNoir[noeud];
  }
  //cout << sommeTotal << endl;
  //cout << "fin" << endl;
}
pair<int, int> requetes[Nmin];
#undef int

std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,
                                       std::vector<int> B, std::vector<int> E) {
  #define int long long
  sommeTotal = 0;
  int Q = (int)E.size();
  int N = W.size();
  for(int i = 0; i < Q; i++)
  {
    requetes[i] = {E[i], i};
  }
  sort(requetes, requetes+Q);
  for(int i = 0; i < N; i++)
  {
    infos[i] = {W[i], T(A[i], B[i])};
  }
  sort(infos, infos+N);

  for(int i = 1; i < N; i++)
  {
    aretes.push_back({infos[i].first-infos[i-1].first, pair<int, int>(i-1, i)});
    if(i >= 2)
      aretes.push_back({infos[i].first-infos[i-2].first, pair<int, int>(i-2, i)});
  }
  sort(aretes.begin(), aretes.end());
  //aVoir
  for(int i = 0; i < N; i++)
  {
    boss[i] = i;
    taille[i] = 1;
    sommeTotal += infos[i].second.normal;
    sommeB[i] = infos[i].second.enPair;
    sommeComposante[i] = infos[i].second.normal;
    if(i % 2 == 0)
    {
      minRouge[i] = (infos[i].second.normal - infos[i].second.enPair);
      minNoir[i] = INFINI;

      
    }
    else
    {
      minNoir[i] = (infos[i].second.normal- infos[i].second.enPair);
      minRouge[i] = INFINI;

    }
    
  }

  //cout << endl;
  //cout << sommeTotal << endl;
  std::vector<long long> R(Q);
  int iEnlever = 0;
//  cout << "jhkjhl" << endl;
  for(int i = 0; i < Q; i++)
  {
    //cout << "deb" << endl;
    int D = requetes[i].first;
 //   cout << D << endl;
  //  
    while((iEnlever < aretes.size()) && (aretes[iEnlever].first <= D))
    {
        //cout << aretes[iEnlever].second.first << " " << aretes[iEnlever].second.second << endl;
        merge(aretes[iEnlever].second.first, aretes[iEnlever].second.second);
        //cout << taille[findBoss(aretes[iEnlever].second.first)] << " " << minRouge[findBoss(aretes[iEnlever].second.first)] << " " << minNoir[findBoss(aretes[iEnlever].second.first)]  << endl;
        //cout << sommeTotal << endl;
        iEnlever++;
    }
    
   // cout << sommeTotal << endl;
    R[requetes[i].second] = sommeTotal;
  }
  return R;
}
/** */

Compilation message (stderr)

nile.cpp: In function 'std::vector<long long int> calculate_costs(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
nile.cpp:183:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  183 |     while((iEnlever < aretes.size()) && (aretes[iEnlever].first <= D))
      |            ~~~~~~~~~^~~~~~~~~~~~~~~

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