Submission #1061251

#TimeUsernameProblemLanguageResultExecution timeMemory
106125112345678Reconstruction Project (JOI22_reconstruction)C++17
0 / 100
154 ms372 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define int long long #pragma gcc-optimize("o3, unroll-loops") const int nx=5e2+5, mx=1e3+5; ll n, m, a[mx], b[mx], w[mx], x, q, L[nx], R[nx], dsu[nx]; vector<ll> dp[nx]; priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> add, rem; int find(int x) { if (dsu[x]==x) return x; return dsu[x]=find(dsu[x]); } bool isused(ll idx, ll cw) { for (int i=1; i<=n; i++) dsu[i]=i; vector<pair<ll, ll>> v; for (int i=1; i<=m; i++) v.push_back({abs(w[i]-cw), i}); sort(v.begin(), v.end()); for (auto [_, i]:v) { if (find(a[i])==find(b[i])) { return 0; continue; } dsu[find(a[i])]=find(b[i]); if (i==idx) return 1; } } int32_t main() { cin.tie(NULL)->sync_with_stdio(false); cin>>n>>m; for (int i=1; i<=m; i++) cin>>a[i]>>b[i]>>w[i]; for (int i=1; i<=m; i++) { if (!isused(i, w[i])) continue; ll l=1, r=w[i]; while (l<r) { ll md=(l+r)/2; if (isused(i, md)) r=md; else l=md+1; } add.push({l, i}); l=w[i], r=2e9; while (l<r) { ll md=(l+r+1)/2; if (isused(i, md)) l=md; else r=md-1; } rem.push({l, i}); } cin>>q; set<ll> edg; while (q--) { cin>>x; while (!add.empty()&&add.top().first<=x) edg.insert(add.top().second), add.pop(); while (!rem.empty()&&rem.top().first<x) edg.erase(rem.top().second), rem.pop(); ll res=0; for (auto tmp:edg) res+=abs(w[tmp]-x); //cout<<tmp<<' '<<a[tmp]<<' '<<b[tmp]<<' '<<w[tmp]<<'\n'; cout<<res<<'\n'; } }

Compilation message (stderr)

reconstruction.cpp:7: warning: ignoring '#pragma gcc ' [-Wunknown-pragmas]
    7 | #pragma gcc-optimize("o3, unroll-loops")
      | 
reconstruction.cpp: In function 'bool isused(long long int, long long int)':
reconstruction.cpp:24:26: warning: control reaches end of non-void function [-Wreturn-type]
   24 |     vector<pair<ll, ll>> v;
      |                          ^
#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...