제출 #1198032

#제출 시각아이디문제언어결과실행 시간메모리
1198032LucaIlieReconstruction Project (JOI22_reconstruction)C++20
42 / 100
5097 ms413672 KiB
#include <bits/stdc++.h> using namespace std; struct edge { int u, v, w; }; struct DSU { vector<int> parent; void init(int n) { parent.clear(); parent.resize(n + 1); for (int i = 0; i <= n; i++) parent[i] = i; } int findParent(int v) { if (parent[v] != v) parent[v] = findParent(parent[v]); return parent[v]; } void connect(int u, int v) { u = findParent(u); v = findParent(v); if (u == v) return; parent[v] = u; } bool connected(int u, int v) { u = findParent(u); v = findParent(v); return (u == v); } }; const int MAX_N = 500; const int MAX_M = 1e5; const int MAX_Q = 1e6; vector<int> importantEdgesLower[MAX_M + 1], importantEdgesGreater[MAX_M + 2]; edge edges[MAX_M + 1]; DSU dsu; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; for (int e = 1; e <= m; e++) cin >> edges[e].u >> edges[e].v >> edges[e].w; sort(edges + 1, edges + 1 + m, [](edge a, edge b) { return a.w < b.w; }); for (int e = 1; e <= m; e++) { dsu.init(n); dsu.connect(edges[e].u, edges[e].v); importantEdgesLower[e].push_back(e); for (int f: importantEdgesLower[e - 1]) { if (!dsu.connected(edges[f].u, edges[f].v)) { dsu.connect(edges[f].u, edges[f].v); importantEdgesLower[e].push_back(f); } } } for (int e = m; e >= 1; e--) { dsu.init(n); dsu.connect(edges[e].u, edges[e].v); importantEdgesGreater[e].push_back(e); for (int f: importantEdgesGreater[e + 1]) { if (!dsu.connected(edges[f].u, edges[f].v)) { dsu.connect(edges[f].u, edges[f].v); importantEdgesGreater[e].push_back(f); } } } int q; cin >> q; for (int i = 0; i < q; i++) { int w; cin >> w; int l = 0, r = m + 1; while (r - l > 1) { int mid = (l + r) / 2; if (edges[mid].w > w) r = mid; else l = mid; } dsu.init(n); int j = 0; long long cost = 0; for (int e: importantEdgesLower[l]) { while (j < (int)importantEdgesGreater[r].size() && edges[importantEdgesGreater[r][j]].w - w < w - edges[e].w) { int f = importantEdgesGreater[r][j]; if (!dsu.connected(edges[f].u, edges[f].v)) { dsu.connect(edges[f].u, edges[f].v); cost += edges[f].w - w; } j++; } if (!dsu.connected(edges[e].u, edges[e].v)) { dsu.connect(edges[e].u, edges[e].v); cost += w - edges[e].w; } } while (j < (int)importantEdgesGreater[r].size()) { int f = importantEdgesGreater[r][j]; if (!dsu.connected(edges[f].u, edges[f].v)) { dsu.connect(edges[f].u, edges[f].v); cost += edges[f].w - w; } j++; } cout << cost << "\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...