| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 884716 | 406 | Reconstruction Project (JOI22_reconstruction) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC optimize ("O3,unroll-loops")
#pragma GCC target("avx2,tune=native")
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define int long long
using namespace std;
using ar = array<int, 2>;
using ar3 = array<int, 3>;
using ar4 = array<int, 4>;
const int M = 1e5 + 5, N = 1002, Q = 1e6 + 5;
const long long INF = 1e9 + 2;
int n, m;
ar4 E[M];
vector<ar4> bk;
inline namespace dsu {
short dpr[N], rk[N];
void init(int n = N / 2) {
memset(rk, 0, n * sizeof rk[0]);
iota(dpr, dpr + n, 0);
}
int gpr(int x) {
while (dpr[x] != x) {
dpr[x] = dpr[dpr[x]];
x = dpr[x];
}
return x;
}
bool merge(int u, int v) {
u = gpr(u), v = gpr(v);
dpr[u] = v;
return u != v;
}
}
int validate(vector<ar4> &E) {
dsu::init();
for (int i = (int) E.size() - 1; ~i; --i) {
auto [w, u, v, id] = E[i];
//cout << "MERGIN " << u + 1 << ' ' << v + 1 << ' ' << w << ' ' << id + 1 << endl;
if (!dsu::merge(u, v)) {
E.erase(E.begin() + i);
return id;
}
}
return -1;
}
int R[M], L[M];
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
vector<ar3> V;
FOR(i, 0, m) {
cin >> E[i][1] >> E[i][2] >> E[i][0];
--E[i][1], --E[i][2];
if (E[i][1] > E[i][2]) swap(E[i][1], E[i][2]);
V.push_back({E[i][0], E[i][0] * -2ll, 2ll});
}
sort(E, E + m);
FOR(i, 0, m) E[i][3] = i;
FOR(i, 0, m) {
auto &[w, u, v, id1] = E[i];
bk.insert(lower_bound(bk.begin(), bk.end(), E[i]), E[i]);
int id = validate(bk);
//cout << "AT : " << i + 1 << " ID: " << id + 1 << endl;
if (id == -1) {
L[i] = -INF;
}
else {
assert(E[id][0] <= w);
L[i] = (w + E[id][0] + 1) / 2;
assert(L[i] <= w);
R[id] = (w + E[id][0] + 1) / 2;
assert(R[id] >= E[id][0]);
V.push_back({R[id], E[id][0], -1});
//cout << "PUSING " << R[id] << ' ' << E[id][0] << ' ' << -1 << endl;
}
V.push_back({L[i], E[i][0], -1});
//cout << "PUSING " << L[i] << ' ' << E[i][0] << ' ' << -1 << endl;
}
//cout << "BAZE " << endl;
sort(V.rbegin(), V.rend());
int q; cin >> q;
int S = 0, td = 0;
FOR(i, 0, q) {
int x; cin >> x;
while (V.size() && V.back()[0] <= x) {
auto a = V.back();
//cout << a[0] << ' ' << a[1] << ' ' << a[2] << endl;
V.pop_back();
S += a[1];
td += a[2];
}
//cout << "T: " << td << ' ' << S << endl;
cout << S + x * td << '\n';
}
return 0;
}