Submission #1106495

#TimeUsernameProblemLanguageResultExecution timeMemory
1106495Noname_1900Nile (IOI24_nile)C++17
51 / 100
86 ms19140 KiB
#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))
      |            ~~~~~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...