Submission #544946

#TimeUsernameProblemLanguageResultExecution timeMemory
544946benson1029Reconstruction Project (JOI22_reconstruction)C++14
70 / 100
5049 ms826640 KiB
#include<bits/stdc++.h> using namespace std; #pragma GCC target ("avx2") #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") 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); } 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] = 2e9; 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(v>=x[i] && v<=y[i]) { ans += abs(v-edg[i].first); } } cout << ans << "\n"; } }

Compilation message (stderr)

reconstruction.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("O3")
      | 
reconstruction.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("unroll-loops")
      |
#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...