Submission #1107085

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107085		helloWorld7846854	Nile (IOI24_nile)	C++17	100 / 100	86 ms	32036 KiB

nile

// helloWorld7846854

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct Composante
{
    int minPair, minImpair, size;
    int prix;

    int getRealPrice()
    {
        if (size % 2 == 0)
        {
            return prix;
        }
        else
        {
            return prix + minImpair;
        }
    }
};
struct Event
{
    bool type;
    int d, idRequest;
    pair<int, int> arete;
    Event() {}
    Event(int t, pair<int, int> inter) : arete(inter), d(t) { type = false; }
    Event(int t, int idReq) : idRequest(idReq), d(t) { type = true; }
    bool operator<(const Event &autre)
    {
        if (d == autre.d)
        {
            if (!type && !autre.type)
            {
                return arete.second - arete.first < autre.arete.second - autre.arete.first;
            }
            return !type && autre.type;
        }
        return d < autre.d;
    }
};

struct Relique
{
    int w, a, b;
    bool operator<(const Relique &autre)
    {
        return w < autre.w;
    }
};
template <typename T>
void minEgal(T &a, T b)
{
    a = min(a, b);
}

struct DSU
{
    vector<int> boss;
    vector<Composante> composantes;
    vector<Relique> reliques;
    long long cost;
    Composante merge(Composante deb, Composante end)
    {
        Composante res;
        if (deb.size % 2 == 0)
        {
            res.minImpair = min(deb.minImpair, end.minImpair);
            res.minPair = min(deb.minPair, end.minPair);
        }
        else
        {
            res.minImpair = min(deb.minImpair, end.minPair);
            res.minPair = min(deb.minPair, end.minImpair);
        }
        res.size = deb.size + end.size;
        res.prix = deb.prix + end.prix;
        return res;
    }

    DSU(int size, vector<Relique> re)
    {
        boss.resize(size, -1);
        composantes.resize(size);
        reliques = re;
        cost = 0;
        for (auto &&relique : reliques)
        {
            cost += relique.a;
        }
        for (int i = 0; i < size; i++)
        {
            composantes[i].minImpair = reliques[i].a - reliques[i].b;
            composantes[i].minPair = 1e9 + 20;
            composantes[i].prix = reliques[i].b;
            composantes[i].size = 1;
        }
    }

    int parent(int i)
    {
        if (boss[i] == -1 || boss[i] == i)
            return i;
        return boss[i] = parent(boss[i]);
    }

    void merge(int a, int b)
    {
        int parenta = parent(a);
        int parentb = parent(b);

        if (parenta == parentb)
        {
            cost = cost - composantes[parenta].getRealPrice();
            if (a + 2 == b)
            {
                minEgal(composantes[parenta].minImpair, reliques[a + 1].a - reliques[a + 1].b);
                minEgal(composantes[parenta].minPair, reliques[a + 1].a - reliques[a + 1].b);
            }
            cost = cost + composantes[parenta].getRealPrice();
        }

        else
        {
            Composante merged = merge(composantes[parenta], composantes[parentb]);

            cost = cost - composantes[parenta].getRealPrice() - composantes[parentb].getRealPrice() + merged.getRealPrice();
            int parent = boss[parentb] = parenta;
            composantes[parent] = merged;
        }
    }

    long long getCost()
    {

        return cost;
    }
};

vector<long long> calculate_costs(vector<signed> W, vector<signed> A, vector<signed> B, vector<signed> E)
{
    int nbReliques = W.size();
    int nbRequests = E.size();
    // for (int i = 0; i < nbReliques; i++)
    // {
    //     cerr << W[i] << " " << A[i] << " " << B[i] << endl;
    // }
    // for (auto &&i : E)
    // {
    //     cerr << i << endl;
    // }

    vector<Relique> reliques(nbReliques);
    for (int i = 0; i < nbReliques; i++)
    {
        reliques[i] = {W[i], A[i], B[i]};
    }

    sort(reliques.begin(), reliques.end());

    vector<Event> events(0);
    for (int i = 0; i < nbRequests; i++)
    {
        events.push_back(Event(E[i], i));
    }
    for (int i = 0; i < nbReliques; i++)
    {
        if (i < nbReliques - 1)
        {
            events.push_back(Event(reliques[i + 1].w - reliques[i].w, {i, i + 1}));
        }
        if (i < nbReliques - 2)
        {
            events.push_back(Event(reliques[i + 2].w - reliques[i].w, {i, i + 2}));
        }
    }
    sort(events.begin(), events.end());
    DSU composantes(nbReliques, reliques);

    vector<long long> Res(nbRequests, 0);
    for (auto &&event : events)
    {
        // cerr << event.type << " " << event.d << " " << composantes.getCost();
        // if (!event.type)
        //     cerr << " "
        //          << event.arete.first << " " << event.arete.second;
        // cerr << endl;
        if (event.type)
            Res[event.idRequest] = composantes.getCost();
        else
            composantes.merge(event.arete.first, event.arete.second);
    }

    // for (auto &&i : Res)
    // {
    //     cout << i << endl;
    // }
    // cout << Res.size();
    return Res;
}

Compilation message (stderr)

nile.cpp: In constructor 'Event::Event(long long int, std::pair<long long int, long long int>)':
nile.cpp:28:20: warning: 'Event::arete' will be initialized after [-Wreorder]
   28 |     pair<int, int> arete;
      |                    ^~~~~
nile.cpp:27:9: warning:   'long long int Event::d' [-Wreorder]
   27 |     int d, idRequest;
      |         ^
nile.cpp:30:5: warning:   when initialized here [-Wreorder]
   30 |     Event(int t, pair<int, int> inter) : arete(inter), d(t) { type = false; }
      |     ^~~~~
nile.cpp: In constructor 'Event::Event(long long int, long long int)':
nile.cpp:27:12: warning: 'Event::idRequest' will be initialized after [-Wreorder]
   27 |     int d, idRequest;
      |            ^~~~~~~~~
nile.cpp:27:9: warning:   'long long int Event::d' [-Wreorder]
   27 |     int d, idRequest;
      |         ^
nile.cpp:31:5: warning:   when initialized here [-Wreorder]
   31 |     Event(int t, int idReq) : idRequest(idReq), d(t) { type = true; }
      |     ^~~~~

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