Submission #1087692

#TimeUsernameProblemLanguageResultExecution timeMemory
1087692vladiliusReconstruction Project (JOI22_reconstruction)C++17
70 / 100
5056 ms426740 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 dsu1{ int sz[N + 1], p[N + 1], n; vector<int> ed; ll W; dsu1(int ns){ n = ns; } int get(int v){ if (p[v] != v){ p[v] = get(p[v]); } return p[v]; } void unite(int x, int y, int w){ 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]; W += w; ed.pb(w); } void clear(){ for (int i = 1; i <= n; i++){ p[i] = i; sz[i] = 1; } ed.clear(); W = 0; } }; struct dsu{ int sz[N + 1], p[N + 1], n; ll W; dsu(int ns){ n = ns; } int get(int v){ if (p[v] != v){ p[v] = get(p[v]); } return p[v]; } void unite(int x, int y, int w){ 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]; W += w; } void clear(){ for (int i = 1; i <= n; i++){ p[i] = i; sz[i] = 1; } W = 0; } }; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin>>n>>m; vector<arr3> ed = {{0, 0, 0}}; for (int i = 1; i <= m; i++){ int a, b, w; cin>>a>>b>>w; ed.pb({a, b, w}); } ed.pb({0, 0, inf}); auto cmp = [&](arr3& x, arr3& y){ return x[2] < y[2]; }; sort(ed.begin(), ed.end(), cmp); vector<int> actl[m + 2]; dsu1 T1(n); for (int i = 1; i <= m; i++){ T1.clear(); T1.unite(ed[i][0], ed[i][1], i); for (int j: actl[i - 1]){ T1.unite(ed[j][0], ed[j][1], j); } actl[i] = T1.ed; } vector<int> actr[m + 2]; for (int i = m; i > 0; i--){ T1.clear(); T1.unite(ed[i][0], ed[i][1], i); for (int j: actr[i + 1]){ T1.unite(ed[j][0], ed[j][1], j); } actr[i] = T1.ed; } int q; cin>>q; vector<pii> qs; for (int i = 1; i <= q; i++){ int x; cin>>x; qs.pb({x, i}); } sort(qs.begin(), qs.end()); vector<ll> out(q + 1); int j1 = 0; dsu T(n); for (int i = 0; i <= m; i++){ vector<int>& edg1 = actl[i], edg2 = actr[i + 1]; int l = ed[i][2], r = ed[i + 1][2] - 1; int j2 = j1; while (j2 < qs.size() && l <= qs[j2].ff && qs[j2].ff <= r){ j2++; } while (j1 < j2){ int x = qs[j1].ff; int i1 = 0, i2 = 0; T.clear(); while (i1 < edg1.size() || i2 < edg2.size()){ if (i1 == edg1.size()){ int j = edg2[i2]; T.unite(ed[j][0], ed[j][1], abs(ed[j][2] - x)); i2++; continue; } if (i2 == edg2.size()){ int j = edg1[i1]; T.unite(ed[j][0], ed[j][1], abs(ed[j][2] - x)); i1++; continue; } int v1 = abs(ed[edg1[i1]][2] - x); int v2 = abs(ed[edg2[i2]][2] - x); if (v1 < v2){ int j = edg1[i1]; T.unite(ed[j][0], ed[j][1], v1); i1++; } else { int j = edg2[i2]; T.unite(ed[j][0], ed[j][1], v2); i2++; } } out[qs[j1].ss] = T.W; j1++; } } for (int i = 1; i <= q; i++) cout<<out[i]<<"\n"; }

Compilation message (stderr)

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:131:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |         while (j2 < qs.size() && l <= qs[j2].ff && qs[j2].ff <= r){
      |                ~~~^~~~~~~~~~~
reconstruction.cpp:138:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |             while (i1 < edg1.size() || i2 < edg2.size()){
      |                    ~~~^~~~~~~~~~~~~
reconstruction.cpp:138:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |             while (i1 < edg1.size() || i2 < edg2.size()){
      |                                        ~~~^~~~~~~~~~~~~
reconstruction.cpp:139:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |                 if (i1 == edg1.size()){
      |                     ~~~^~~~~~~~~~~~~~
reconstruction.cpp:145:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |                 if (i2 == edg2.size()){
      |                     ~~~^~~~~~~~~~~~~~
#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...