| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1106575 | 2024-10-30T16:47:30 Z | helloWorld7846854 | 나일강 (IOI24_nile) | C++17 | 0 ms | 0 KB |
// helloWorld7846854
#include "nile.h"
#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;
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<int> W, vector<int> A, vector<int> B, vector<int> E)
{
int nbReliques = W.size();
int nbRequests = E.size();
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<long long> Res(nbRequests, 0);
vector<Event> events;
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);
for (auto &&event : events)
{
if (event.type)
Res[event.idRequest] = composantes.getCost();
else
composantes.merge(event.arete.first, event.arete.second);
}
return Res;
}