제출 #874547

#제출 시각아이디문제언어결과실행 시간메모리
874547406Reconstruction Project (JOI22_reconstruction)C++17
3 / 100
5084 ms11544 KiB
#pragma GCC optimize ("Ofast,unroll-loops") #pragma GCC target("avx2") //besmellah #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))) using namespace std; using ar = array<int, 2>; using ar3 = array<int, 3>; const int M = 1e5 + 5, N = 505, Q = 1e6 + 5; const long long INF = 1ll << 30; namespace dsu { int dpr[N]; void init() { iota(dpr, dpr + N, 0); //memset(dpr, -1, sizeof dpr); } int gpr(int x) { return dpr[x] == x ? x : dpr[x] = gpr(dpr[x]); } bool merge(int u, int v) { u = gpr(u), v = gpr(v); if (u == v) return false; dpr[u] = v; return true; } } vector<ar> adj[N]; int n, m; ar3 W[N], E[M], hame[2 * N]; bitset<N> seen; void dfs(int v, int p) { seen[v] = true; for (auto [u, w]: adj[v]) if (u != p) { W[u] = max(W[v], {w, u, v}); dfs(u, v); } } 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); vector<ar3> undo; deque<ar3> Es; for (int i = m - 1; i >= 0; i--) { //ino mishe behtar kard ba DSU vali halesh nist (orderesham ye log kamtar dare) auto [w, u, v] = E[i]; W[u] = {-INF, u, u}; seen = 0; dfs(u, u); if (seen[v]) { auto [dw, du, dv] = W[v]; if (du > dv) swap(du, dv); ers(du, (ar{dv, dw})); ers(dv, (ar{du, dw})); Es.erase(find(Es.begin(), Es.end(), ar3{dw, du, dv})); //cout << "DELETING " << du + 1 << ' ' << dv + 1 << " " << dw << endl; undo.push_back({dw, du, dv}); } else undo.push_back({-1, -1, -1}); //cout << "ADDING " << u + 1 << ' ' << v + 1 << ' ' << w << endl; Es.push_back(E[i]); adj[v].push_back({u, w}); adj[u].push_back({v, w}); } //for (auto [w, u, v]: Es) cout << u << ' ' << v << ' ' << w << endl; //now MST at zero vector<ar3> jelo; //be zaman ahamiat nemidaham int q; cin >> q; int p = 0; while (q--) { int x; cin >> x; bool t = false; while (p < m && E[p][0] < x) { //ino hesesh bood vali log ziad dare jelo.push_back(E[p]); t = true; Es.erase(find(Es.begin(), Es.end(), E[p])); auto akh = undo.back(); undo.pop_back(); if (akh[0] != -1) Es.push_back(akh); ++p; sort(Es.begin(), Es.end()); } if (t) { vector<ar3> ok; ok.reserve(jelo.size()); dsu::init(); sort(jelo.rbegin(), jelo.rend()); for (auto [w, u, v]: jelo) if (dsu::merge(u, v)) ok.push_back({w, u, v}); jelo = ok; } //jelo -> small to large (x - w) //Es -> small to large (x - w) int p1 = 0, p2 = 0; while (p1 != jelo.size() || p2 != Es.size()) { if (p2 == Es.size() || (p1 != jelo.size() && (x - jelo[p1][0]) < (Es[p2][0] - x))) hame[p1 + p2] = jelo[p1], ++p1; else hame[p1 + p2] = Es[p2], ++p2; } dsu::init(); long long ans = 0; int cnt = 0; FOR(i, 0, p1 + p2) { auto [w, u, v] = hame[i]; w = abs(x - w); if (dsu::merge(u, v)) { ans += w; ++cnt; if (cnt == n - 1) break; } } cout << ans << '\n'; } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:109:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |                 while (p1 != jelo.size() || p2 != Es.size()) {
      |                        ~~~^~~~~~~~~~~~~~
reconstruction.cpp:109:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |                 while (p1 != jelo.size() || p2 != Es.size()) {
      |                                             ~~~^~~~~~~~~~~~
reconstruction.cpp:110:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |                         if (p2 == Es.size() || (p1 != jelo.size() && (x - jelo[p1][0]) < (Es[p2][0] - x)))
      |                             ~~~^~~~~~~~~~~~
reconstruction.cpp:110:52: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |                         if (p2 == Es.size() || (p1 != jelo.size() && (x - jelo[p1][0]) < (Es[p2][0] - x)))
      |                                                 ~~~^~~~~~~~~~~~~~
#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...