Submission #1106290

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106290		Quentolosse	Nile (IOI24_nile)	C++17	0 / 100	42 ms	18936 KiB

nile

#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<signed> W, vector<signed> A, vector<signed> B, vector<signed> 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;
    
}

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