Submission #1106288

#TimeUsernameProblemLanguageResultExecution timeMemory
1106288QuentolosseNile (IOI24_nile)C++17
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> #include "nile.h" #define int long long using namespace std; struct Event { int type; int temps; pair<int,int> arrete; int iRequete; Event(int _t, pair<int,int> _a) { temps = _t; type = 1; arrete = _a; } Event(int _t, int _i) { temps = _t; type = 2; iRequete = _i; } bool operator < (const Event& other) { if (temps == other.temps) { return type < other.type; } return temps < other.temps; } }; struct Relique { int poids, a, b; bool operator < (const Relique& other) { return poids < other.poids; } }; vector<Relique> reliques; struct Composante { int min[2] = {(int)1e18, (int)1e18}; int taille = 1; }; struct DSU { vector<int> parents; vector<Composante> composantes; int somme_composantes = 0; DSU(int taille) { parents.resize(taille); composantes.resize(taille); for (int i = 0; i < taille; i++) { parents[i] = -1; composantes[i].min[0] = reliques[i].a - reliques[i].b; somme_composantes += reliques[i].a - reliques[i].b; } } int parent(int pos) { if (parents[pos] == -1) return pos; int ret = parent(parents[pos]); parents[pos] = ret; return ret; } void merge(int relique1, int relique2) { if (relique1 > relique2) swap(relique1, relique2); int parent1 = parent(relique1); int parent2 = parent(relique2); Composante c1 = composantes[parent1]; Composante c2 = composantes[parent1]; somme_composantes -= c1.min[0] + c2.min[0]; Composante nouvelle; nouvelle.taille = c1.taille + c2.taille; if (c1.taille % 2) { nouvelle.min[0] = min(c1.min[0], c2.min[1]); nouvelle.min[1] = min(c1.min[1], c2.min[0]); } else { nouvelle.min[0] = min(c1.min[0], c2.min[0]); nouvelle.min[1] = min(c1.min[1], c2.min[1]); } somme_composantes += nouvelle.min[0]; if (c1.taille < c2.taille) { parents[parent1] = parent2; composantes[parent2] = nouvelle; } else { parents[parent2] = parent1; composantes[parent1] = nouvelle; } } }; vector<int> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) { int nbReliques = W.size(); int nbRequetes = E.size(); vector<Event> evenements; for (int i = 0; i < nbRequetes; i++) { evenements.push_back(Event(E[i], i)); } for (int i = 0; i < nbReliques; i++) { reliques.push_back(Relique{W[i], A[i], B[i]}); } sort(reliques.begin(), reliques.end()); for (int i = 0; i < nbReliques - 1; i++) { evenements.push_back(Event(reliques[i+1].poids - reliques[i].poids, make_pair(i, i+1))); } for (int i = 0; i < nbReliques - 2; i++) { evenements.push_back(Event(reliques[i+2].poids - reliques[i].poids, make_pair(i, i+2))); } DSU dsu(nbReliques); vector<int> ret(nbRequetes); sort(evenements.begin(), evenements.end()); for (auto &&event : evenements) { if (event.type == 1) { int relique1 = event.arrete.first, relique2 = event.arrete.second; if (relique2 - relique1 == 1) { dsu.merge(relique1, relique2); } else { Composante c = dsu.composantes[dsu.parent(relique1 + 1)]; c.min[0] = min(c.min[0], reliques[relique1 + 1].a - reliques[relique1 + 1].b); c.min[1] = min(c.min[1], reliques[relique1 + 1].a - reliques[relique1 + 1].b); } } else { ret[event.iRequete] = dsu.somme_composantes; } } int somme_b = 0; for (auto &&i : reliques) { somme_b += i.b; } for (auto &&i : ret) { i += somme_b; } return ret; }

Compilation message (stderr)

/usr/bin/ld: /tmp/ccBUY7F0.o: in function `main':
grader.cpp:(.text.startup+0x300): undefined reference to `calculate_costs(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status