제출 #751853

#제출 시각아이디문제언어결과실행 시간메모리
751853puppyReconstruction Project (JOI22_reconstruction)C++17
3 / 100
5077 ms786480 KiB
#include <iostream> #include <vector> #include <algorithm> #include <queue> #define all(v) v.begin(), v.end() using namespace std; struct UnionFind { vector<int> par; void init(int n){par.resize(n+1); for(int i=1;i<=n;i++) par[i] = i;} int fin(int i){return i==par[i]?i:(par[i] = fin(par[i]));} void uni(int u, int v){par[fin(u)] = fin(v);} bool isuni(int u, int v){return fin(u) == fin(v);} }; int N, M; vector<int> inc[2][100005]; struct Edge { int s, e; int w; bool operator<(const Edge &e) { return w < e.w; } }; Edge edge[100005]; vector<pair<int, int>> adj[505]; bool visited[505]; pair<int, int> par[505]; signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> N >> M; for (int i = 1; i <= M; i++) { int a, b, w; cin >> a >> b >> w; edge[i] = {a, b, w}; } sort(edge + 1, edge + M + 1); for (int k = 0; k < 2; k++) { for (int i = 1; i <= M; i++) { fill(visited + 1, visited + N + 1, false); for (int t:inc[k][i-1]) inc[k][i].push_back(t); int a = edge[i].s, b = edge[i].e; visited[a] = true; queue<int> q; q.push(a); while (!q.empty()) { int cur = q.front(); q.pop(); for (pair<int, int> p:adj[cur]) { if (!visited[p.second]) { par[p.second] = make_pair(p.first, cur); visited[p.second] = true; q.push(p.second); } } } if (visited[b]) { int mn = i, now = b; while (1) { mn = min(mn, par[now].first); now = par[now].second; if (now == a) break; } inc[k][i].erase(remove(inc[k][i].begin(), inc[k][i].end(), mn), inc[k][i].end()); inc[k][i].push_back(i); int s = edge[mn].s, e = edge[mn].e; adj[s].erase(remove(all(adj[s]), make_pair(mn, e)), adj[s].end()); adj[e].erase(remove(all(adj[e]), make_pair(mn, s)), adj[e].end()); } adj[a].push_back(make_pair(i, b)); adj[b].push_back(make_pair(i, a)); inc[k][i].push_back(i); inc[k][i].shrink_to_fit(); } for (int i = 1; i <= N; i++) adj[i].clear(); reverse(edge + 1, edge + M + 1); } for (int i = 1; i <= M / 2; i++) swap(inc[1][i], inc[1][M+1-i]); for (int i = 1; i <= M; i++) { for (int &k:inc[1][i]) k = M + 1 - k; sort(inc[0][i].begin(), inc[0][i].end(), greater<int>()); sort(inc[1][i].begin(), inc[1][i].end(), less<int>()); } UnionFind uf; int pv = 0; int Q; cin >> Q; for (int i = 0; i < Q; i++) { int X; cin >> X; while (pv < M && edge[pv+1].w <= X) pv++; int l = 0, r = 0; uf.init(N); int cnt = N - 1; long long ans = 0; while (cnt) { bool dec = false; if (l == (int)inc[0][pv].size()) dec = true; else if (r == (int)inc[1][pv+1].size()) dec = false; else dec = (X - edge[inc[0][pv][l]].w <= edge[inc[1][pv+1][r]].w - X) ? false : true; int use = dec ? inc[1][pv+1][r++] : inc[0][pv][l++]; if (!uf.isuni(edge[use].s, edge[use].e)) { uf.uni(edge[use].s, edge[use].e); ans += abs(edge[use].w - X); cnt--; } } cout << ans << '\n'; } }
#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...