Submission #1087941

#TimeUsernameProblemLanguageResultExecution timeMemory
1087941vladiliusReconstruction Project (JOI22_reconstruction)C++17
100 / 100
1579 ms443056 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") using namespace std; using ll = long long; using pii = pair<int, int>; #define pb push_back #define ff first #define ss second #define ins insert #define arr3 array<int, 3> const int inf = 1e9 + 5; const int N = 5e2; struct dsu{ int sz[N + 1], p[N + 1]; int n; void init(int ns){ n = ns; for (int i = 1; i <= n; i++){ p[i] = i; sz[i] = 1; } } int get(int v){ if (p[v] != v){ p[v] = get(p[v]); } return p[v]; } void unite(int x, int y){ x = get(x); y = get(y); if (x == y) return; if (sz[x] > sz[y]) swap(x, y); p[x] = y; sz[y] += sz[x]; } bool same(int x, int y){ return get(x) == get(y); } void clear(){ for (int i = 1; i <= n; i++){ p[i] = i; sz[i] = 1; } } }; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin>>n>>m; vector<arr3> ed; for (int i = 1; i <= m; i++){ int a, b, w; cin>>a>>b>>w; ed.pb({a, b, w}); } int q; cin>>q; vector<int> x(q + 1); vector<ll> out(q + 1); for (int i = 1; i <= q; i++){ cin>>x[i]; } auto cmp = [&](arr3& x, arr3& y){ return x[2] < y[2]; }; sort(ed.begin(), ed.end(), cmp); vector<int> ws; for (int i = 0; i < m; i++) ws.pb(ed[i][2]); vector<int> :: iterator it1, it2; dsu T[m]; for (int i = 0; i < m; i++) T[i].init(n); vector<ll> p1(q + 2); vector<int> p2(q + 2); for (int i = m - 1; i >= 0; i--){ auto [a, b, w] = ed[i]; int l = i, r = m - 1; while (l + 1 < r){ int k = (l + r) / 2; if (T[k].same(a, b)){ r = k - 1; } else { l = k; } } if (!T[r].same(a, b)) l = r; if (l == (m - 1)) l = inf; else l = (ws[l + 1] + w - 1) / 2; it1 = lower_bound(x.begin() + 1, x.end(), w); it2 = upper_bound(x.begin() + 1, x.end(), l); l = (int) (it1 - x.begin()); r = (int) (it2 - x.begin()); if (l > r) continue; p1[l] -= w; p1[r] += w; p2[l]++; p2[r]--; for (int j = i; j < m; j++){ if (T[j].same(a, b)) break; T[j].unite(a, b); } } for (int i = 0; i < m; i++) T[i].clear(); for (int i = 0; i < m; i++){ auto [a, b, w] = ed[i]; int l = 0, r = i; while (l + 1 < r){ int k = (l + r) / 2; if (T[k].same(a, b)){ l = k + 1; } else { r = k; } } if (!T[l].same(a, b)) r = l; if (!r) r = 0; else r = (ws[r - 1] + w + 1) / 2; it1 = lower_bound(x.begin() + 1, x.end(), r); it2 = lower_bound(x.begin() + 1, x.end(), w); l = (int) (it1 - x.begin()); r = (int)(it2 - x.begin()); if (l > r) continue; p1[l] += w; p1[r] -= w; p2[l]--; p2[r]++; for (int j = i; j >= 0; j--){ if (T[j].same(a, b)) break; T[j].unite(a, b); } } ll s1 = 0; int s2 = 0; for (int i = 1; i <= q; i++){ s1 += p1[i]; s2 += p2[i]; cout<<1LL * x[i] * s2 + s1<<"\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...