oj.uz

Submission #1107084

# Submission time Handle Problem Language Result Execution time Memory
1107084 2024-10-31T14:57:36 Z helloWorld7846854 Nile (IOI24_nile) C++17
32 / 100
 87 ms 17856 KB 
// 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

nile.cpp: In constructor 'Event::Event(int, std::pair<int, int>)':
nile.cpp:28:20: warning: 'Event::arete' will be initialized after [-Wreorder]
   28 |     pair<int, int> arete;
      |                    ^~~~~
nile.cpp:27:9: warning:   '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(int, int)':
nile.cpp:27:12: warning: 'Event::idRequest' will be initialized after [-Wreorder]
   27 |     int d, idRequest;
      |            ^~~~~~~~~
nile.cpp:27:9: warning:   '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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 760 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 12292 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 12216 KB Output is correct
2 Correct 42 ms 13564 KB Output is correct
3 Correct 51 ms 13496 KB Output is correct
4 Correct 47 ms 13496 KB Output is correct
5 Correct 43 ms 13732 KB Output is correct
6 Correct 49 ms 12984 KB Output is correct

Subtask #4
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 760 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 760 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 12216 KB Output is correct
2 Correct 42 ms 13564 KB Output is correct
3 Correct 51 ms 13496 KB Output is correct
4 Correct 47 ms 13496 KB Output is correct
5 Correct 43 ms 13732 KB Output is correct
6 Correct 49 ms 12984 KB Output is correct
7 Correct 69 ms 17848 KB Output is correct
8 Correct 79 ms 17324 KB Output is correct
9 Correct 79 ms 17464 KB Output is correct
10 Correct 78 ms 17856 KB Output is correct
11 Correct 74 ms 17384 KB Output is correct
12 Correct 77 ms 17856 KB Output is correct
13 Correct 87 ms 17856 KB Output is correct
14 Correct 67 ms 17080 KB Output is correct
15 Correct 85 ms 17848 KB Output is correct

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 1 ms 760 KB Output isn't correct
3 Halted 0 ms 0 KB -