#include "nile.h"
using namespace std;
#include<bits/stdc++.h>
const int NMAX = 100000;
#define int long long
const int INFINI = 1000000000000ll;
struct T {
int poid, normal, enPair;
T(int prem = 0, int a = 0, int b = 0)
{
poid = prem;
normal = a;
enPair = b;
}
bool operator<(const T &other) const {
return poid < other.poid;
}
};
vector<pair<int, pair<int, int>>> aretes;
int boss[NMAX];
int minRouge[NMAX], minNoir[NMAX];
T infos[NMAX];//W, A, B
int sommeB[NMAX];
int sommeTotal;
int taille[NMAX];
int sommeComposante[NMAX];
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].normal-infos[noeud].enPair));
minNoir[findBoss(noeud)] = min(minNoir[findBoss(noeud)], (infos[noeud].normal-infos[noeud].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)
{
int bossA = findBoss(a), bossB = findBoss(b);
if(bossA == bossB)
{
int balance = a+1;
comparerBalance(balance);
sommeTotal -= sommeComposante[bossA];
}
else
{
int 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];
taille[bossA] += taille[bossB];
sommeTotal -= sommeComposante[bossA] + sommeComposante[bossB];
boss[bossB] = bossA;
}
int noeud = bossA;
if(taille[noeud]%2 == 0)
{
sommeComposante[noeud] = sommeB[noeud];
}
else if(bossA%2 == 0)
{
sommeCo#include "nile.h"
using namespace std;
#include<bits/stdc++.h>
const int NMAX = 100000;
#define int long long
const int INFINI = 1000000000000ll;
struct T {
int poid, normal, enPair;
T(int prem = 0, int a = 0, int b = 0)
{
poid = prem;
normal = a;
enPair = b;
}
bool operator<(const T &other) const {
return poid < other.poid;
}
};
vector<pair<int, pair<int, int>>> aretes;
int boss[NMAX];
int minRouge[NMAX], minNoir[NMAX];
T infos[NMAX];//W, A, B
int sommeB[NMAX];
int sommeTotal;
int taille[NMAX];
int sommeComposante[NMAX];
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].normal-infos[noeud].enPair));
minNoir[findBoss(noeud)] = min(minNoir[findBoss(noeud)], (infos[noeud].normal-infos[noeud].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)
{
int bossA = findBoss(a), bossB = findBoss(b);
if(bossA == bossB)
{
int balance = a+1;
comparerBalance(balance);
sommeTotal -= sommeComposante[bossA];
}
else
{
int 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];
taille[bossA] += taille[bossB];
sommeTotal -= sommeComposante[bossA] + sommeComposante[bossB];
boss[bossB] = bossA;
}
int noeud = bossA;
if(taille[noeud]%2 == 0)
{
sommeComposante[noeud] = sommeB[noeud];
}
else if(bossA%2 == 0)
{
sommeComposante[noeud] = sommeB[noeud]+minRouge[noeud];
}
else
{
sommeComposante[noeud] = sommeB[noeud]+minNoir[noeud];
}
sommeTotal += sommeComposante[noeud];
}
pair<int, int> requetes[NMAX];
#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], A[i], B[i]};
}
sort(infos, infos+N);
for(int i = 1; i < N; i++)
{
aretes.push_back({infos[i].poid-infos[i-1].poid, pair<int, int>(i-1, i)});
if(i >= 2)
aretes.push_back({infos[i].poid-infos[i-2].poid, 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].normal;
sommeB[i] = infos[i].enPair;
sommeComposante[i] = infos[i].normal;
if(i % 2 == 0)
{
minRouge[i] = (infos[i].normal - infos[i].enPair);
minNoir[i] = INFINI;
}
else
{
minNoir[i] = (infos[i].normal- infos[i].enPair);
minRouge[i] = INFINI;
}
}
std::vector<long long> R(Q);
int iEnlever = 0;
for(int i = 0; i < Q; i++)
{
int D = requetes[i].first;
while((iEnlever < aretes.size()) && (aretes[iEnlever].first <= D))
{
merge(aretes[iEnlever].second.first, aretes[iEnlever].second.second);
iEnlever++;
}
R[requetes[i].second] = sommeTotal;
}
return R;
}
/** */osante[noeud] = sommeB[noeud]+minRouge[noeud];
}
else
{
sommeComposante[noeud] = sommeB[noeud]+minNoir[noeud];
}
sommeTotal += sommeComposante[noeud];
}
pair<int, int> requetes[NMAX];
#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], A[i], B[i]};
}
sort(infos, infos+N);
for(int i = 1; i < N; i++)
{
aretes.push_back({infos[i].poid-infos[i-1].poid, pair<int, int>(i-1, i)});
if(i >= 2)
aretes.push_back({infos[i].poid-infos[i-2].poid, 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].normal;
sommeB[i] = infos[i].enPair;
sommeComposante[i] = infos[i].normal;
if(i % 2 == 0)
{
minRouge[i] = (infos[i].normal - infos[i].enPair);
minNoir[i] = INFINI;
}
else
{
minNoir[i] = (infos[i].normal- infos[i].enPair);
minRouge[i] = INFINI;
}
}
std::vector<long long> R(Q);
int iEnlever = 0;
for(int i = 0; i < Q; i++)
{
int D = requetes[i].first;
while((iEnlever < aretes.size()) && (aretes[iEnlever].first <= D))
{
merge(aretes[iEnlever].second.first, aretes[iEnlever].second.second);
iEnlever++;
}
R[requetes[i].second] = sommeTotal;
}
return R;
}
/** */
Compilation message
nile.cpp:88:12: error: stray '#' in program
88 | sommeCo#include "nile.h"
| ^
nile.cpp: In function 'void merge(long long int, long long int)':
nile.cpp:88:5: error: 'sommeCo' was not declared in this scope; did you mean 'sommeB'?
88 | sommeCo#include "nile.h"
| ^~~~~~~
| sommeB
nile.cpp:117:1: error: a function-definition is not allowed here before '{' token
117 | {
| ^
nile.cpp:125:1: error: a function-definition is not allowed here before '{' token
125 | {
| ^
nile.cpp:131:1: error: a function-definition is not allowed here before '{' token
131 | {
| ^
nile.cpp:144:1: error: a function-definition is not allowed here before '{' token
144 | {
| ^
nile.cpp:187:80: error: a function-definition is not allowed here before '{' token
187 | std::vector<int> B, std::vector<int> E) {
| ^
nile.cpp:247:7: error: 'osante' was not declared in this scope
247 | /** */osante[noeud] = sommeB[noeud]+minRouge[noeud];
| ^~~~~~
nile.cpp:93:11: warning: unused variable 'INFINI' [-Wunused-variable]
93 | const int INFINI = 1000000000000ll;
| ^~~~~~
nile.cpp:107:5: warning: unused variable 'boss' [-Wunused-variable]
107 | int boss[NMAX];
| ^~~~
nile.cpp:109:21: warning: unused variable 'minNoir' [-Wunused-variable]
109 | int minRouge[NMAX], minNoir[NMAX];
| ^~~~~~~
nile.cpp:110:3: warning: unused variable 'infos' [-Wunused-variable]
110 | T infos[NMAX];//W, A, B
| ^~~~~
nile.cpp:112:5: warning: unused variable 'sommeTotal' [-Wunused-variable]
112 | int sommeTotal;
| ^~~~~~~~~~
nile.cpp:113:5: warning: unused variable 'taille' [-Wunused-variable]
113 | int taille[NMAX];
| ^~~~~~
nile.cpp:114:5: warning: unused variable 'sommeComposante' [-Wunused-variable]
114 | int sommeComposante[NMAX];
| ^~~~~~~~~~~~~~~
nile.cpp:183:16: warning: unused variable 'requetes' [-Wunused-variable]
183 | pair<int, int> requetes[NMAX];
| ^~~~~~~~
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:310: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]
310 | while((iEnlever < aretes.size()) && (aretes[iEnlever].first <= D))
| ~~~~~~~~~^~~~~~~~~~~~~~~
