Submission #544938

#TimeUsernameProblemLanguageResultExecution timeMemory
544938benson1029Reconstruction Project (JOI22_reconstruction)C++14
70 / 100
5099 ms830108 KiB
#include<bits/stdc++.h> using namespace std; int n, m, q; pair< int, pair<int,int> > edg[100005]; vector<int> f[100005], b[100005], t[100005]; int x[100005], y[100005]; int dsu[100005]; int find(int x) { if(dsu[x]==x) return x; return dsu[x] = find(dsu[x]); } void merge(int x) { dsu[find(edg[x].second.first)] = find(edg[x].second.second); } bool ok(int p, int v) { return ((x[p]==-1 || v>=x[p]) && (y[p]==-1 || v<=y[p])); } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for(int i=1; i<=m; i++) { cin >> edg[i].second.first >> edg[i].second.second >> edg[i].first; } sort(edg+1, edg+m+1); for(int i=1; i<=m; i++) { b[i].push_back(i); for(int j=1; j<=n; j++) dsu[j] = j; bool tmp = false; x[i] = -1; for(int j:b[i-1]) { if(find(edg[j].second.first)!=find(edg[j].second.second)) { merge(j); if(find(edg[i].second.first)==find(edg[i].second.second) && !tmp) { tmp = true; x[i] = (edg[j].first + edg[i].first + 2) / 2; } else b[i].push_back(j); } } } for(int i=m; i>=1; i--) { f[i].push_back(i); for(int j=1; j<=n; j++) dsu[j] = j; bool tmp = false; y[i] = -1; for(int j:f[i+1]) { if(find(edg[j].second.first)!=find(edg[j].second.second)) { merge(j); if(find(edg[i].second.first)==find(edg[i].second.second) && !tmp) { tmp = true; y[i] = (edg[j].first + edg[i].first) / 2; } else f[i].push_back(j); } } } for(int i=0; i<=m; i++) { for(int j:b[i]) t[i].push_back(j); for(int j:f[i+1]) t[i].push_back(j); } cin >> q; while(q--) { int v; cin >> v; int pos = upper_bound(edg+1, edg+m+1, make_pair(v, make_pair((int)1e9, (int)1e9))) - edg - 1; long long ans = 0; for(int i:t[pos]) { if(ok(i, v)) { ans += abs(v-edg[i].first); } } 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...