Submission #876948

#TimeUsernameProblemLanguageResultExecution timeMemory
876948406Reconstruction Project (JOI22_reconstruction)C++17
3 / 100
5060 ms10832 KiB
//#pragma GCC optimize ("O3,unroll-loops") //#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt") //besmellah //accept sho :D #include <bits/stdc++.h> #define FOR(i, a, b) for (int i = (a); i < (b); ++i) #define ers(v, X) adj[v].erase(find(adj[v].begin(), adj[v].end(), (X))) #define int long long using namespace std; using ar = array<int, 2>; using ar3 = array<int, 4>; using ar5 = array<int, 5>; const int M = 1e5 + 5, N = 505, Q = 1e6 + 5; const long long INF = 1ll << 30; namespace dsu { int dpr[N]; void init() { memset(dpr, -1, sizeof dpr); } int gpr(int x) { return dpr[x] < 0 ? x : dpr[x] = gpr(dpr[x]); } bool merge(int u, int v) { u = gpr(u), v = gpr(v); if (u == v) return false; if (dpr[u] < dpr[v]) swap(u, v); dpr[v] += dpr[u]; dpr[u] = v; return true; } } vector<ar> adj[N]; int n, m, W[N], X[Q], ps[Q], L[M], R[M]; ar3 E[M]; bitset<N> seen; vector<ar3> Es, undo, bk; void dfsmn(int v, int p) { seen[v] = true; for (auto [u, w]: adj[v]) if (u != p) { W[u] = min(W[v], w); dfsmn(u, v); } } void build() { FOR(i, 0, n) adj[i].clear(); seen = 0; for (auto [w, u, v, l]: Es) { adj[u].push_back({v, w}); adj[v].push_back({u, w}); } } ar3 validate(vector<ar3> &E) { sort(E.begin(), E.end()); vector<ar3> ok; dsu::init(); ar3 del = {-1, -1, -1, -1}; for (auto [w, u, v, l]: E) { if (dsu::merge(u, v)) ok.push_back({w, u, v, l}); else del = {w, u, v, l}; } E = ok; return del; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m; FOR(i, 0, m) { cin >> E[i][1] >> E[i][2] >> E[i][0]; --E[i][1], --E[i][2]; if (E[i][1] > E[i][2]) swap(E[i][1], E[i][2]); } sort(E, E + m); FOR(i, 0, m) { auto [w, u, v, l] = E[i]; build(); W[u] = INF; dfsmn(u, u); if (seen[v]) E[i][3] = (W[v] + w + 1) / 2; else E[i][3] = -INF; Es.push_back(E[i]); validate(Es); } for (int i = m - 1; i >= 0; --i) { auto [w, u, v, l] = E[i]; bk.push_back(E[i]); undo.push_back(validate(bk)); } int q; cin >> q; int p = 0, minl = -INF, td, W, cnt = 0; //ar3 dar vaghe ar4-e vector<ar3> fr; FOR(i, 0, q) { int x; cin >> x; bool t = false; while (p < m && x >= E[p][0]) { fr.push_back(E[p]); fr.back()[0] *= -1; auto U = undo.back(); undo.pop_back(); bk.erase(find(bk.begin(), bk.end(), E[p])); if (U[0] != -1) bk.push_back(U); //cout << "BK .push() " << U[0] << endl; ++p; t = true; } if (t || x >= minl) { //build_mst() (M bar hadeaksar) assert(++cnt <= 2 * m); validate(fr); dsu::init(); W = td = 0; minl = INF; //al = bk + fr (bt) vector<ar5> al; //badihish //cout <<"QUERY" << endl; for (auto [w, u, v, l]: fr) { //w = -w assert(w <= x); al.push_back({x + w, v, u, l, 0}); //cout << u + 1 << ' ' << v + 1 << ' ' << w << endl; } //cout << "---" << endl; for (auto [w, u, v, l]: bk) { assert(w >= x); al.push_back({w - x, v, u, l, 1}); //cout << u + 1 << ' ' << v + 1 << ' ' << w << endl; } // //cout << "---" << endl; //int ans = 0; sort(al.begin(), al.end(), [&](const auto &X, const auto &Y) {return X[0] < Y[0];}); for (auto [w, v, u, l, t]: al) { w = (t ? w + x : x - w); //cout << u + 1 << ' ' << v + 1 << ' ' << w << endl; if (dsu::merge(u, v)) { //ans += abs(w - x); W += (t ? w : -w); td += (t ? -1 : +1); } else if (t) { minl = min(minl, l); } } //cout << ans << endl; } cout << td * x + W << '\n'; } return 0; }

Compilation message (stderr)

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:93:22: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
   93 |                 auto [w, u, v, l] = E[i];
      |                      ^~~~~~~~~~~~
reconstruction.cpp:153:34: warning: 'W' may be used uninitialized in this function [-Wmaybe-uninitialized]
  153 |                 cout << td * x + W << '\n';
      |                                  ^
reconstruction.cpp:153:28: warning: 'td' may be used uninitialized in this function [-Wmaybe-uninitialized]
  153 |                 cout << td * x + W << '\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...