제출 #781069

#제출 시각아이디문제언어결과실행 시간메모리
781069aZvezdaReconstruction Project (JOI22_reconstruction)C++14
31 / 100
1351 ms16036 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #ifndef LOCAL #define cerr if(false)cerr #endif const ll MAX_N = 2e3 + 10; ll n, m; pair<ll, pair<ll, ll> > edg[MAX_N]; struct { ll par[MAX_N], sz[MAX_N]; vector<ll> now; void reset() { for(ll i = 1; i <= n; i ++) { par[i] = i; sz[i] = 1; } now.resize(0); } ll find(ll x) { if(par[x] == x) { return x; } else { return par[x] = find(par[x]); } } bool merge(ll x, ll y, ll c) { x = find(x); y = find(y); if(x == y) { return false; } if(sz[x] < sz[y]) { swap(x, y); } par[y] = x; sz[x] += sz[y]; now.push_back(c); return true; } } dsu; vector<ll> cand[MAX_N]; ll lft[MAX_N], rght[MAX_N]; signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m; for(ll i = 0; i < m; i ++) { cin >> edg[i].second.first >> edg[i].second.second >> edg[i].first; } sort(edg, edg + m); dsu.reset(); for(ll i = 0; i < m; i ++) { int other = -1; dsu.reset(); dsu.merge(edg[i].second.first, edg[i].second.second, i); if(i != 0) for(const auto j : cand[i - 1]) { if(!dsu.merge(edg[j].second.first, edg[j].second.second, j)) { other = j; } } cand[i] = dsu.now; if(other != -1) { lft[i] = (edg[i].first + edg[other].first + 2ll) / 2ll; rght[other] = (edg[i].first + edg[other].first) / 2ll; } else { lft[i] = -1e12; } rght[i] = 1e12; } priority_queue<pair<ll, pair<ll, ll> > > pq; for(int i = 0; i < m; i ++) { pq.push({-lft[i], {-1, edg[i].first}}); pq.push({-edg[i].first, {0, edg[i].first}}); pq.push({-rght[i] - 1, {1, edg[i].first}}); } ll cntadd = 0; ll cntrem = 0; ll sum = 0; ll q; cin >> q; while(q --) { ll x; cin >> x; while(!pq.empty() && -pq.top().first <= x) { auto curr = pq.top(); pq.pop(); if(curr.second.first == -1) { cntadd ++; sum += curr.second.second; } else if(curr.second.first == 0) { cntadd --; cntrem ++; sum -= curr.second.second * 2ll; } else { cntrem --; sum += curr.second.second; } } ll ans = sum - cntadd * x + cntrem * x; cout << ans << endl; } }
#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...