Submission #884714

#TimeUsernameProblemLanguageResultExecution timeMemory
884714406Reconstruction Project (JOI22_reconstruction)C++17
100 / 100
550 ms38036 KiB
//#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...