Submission #1093740

#TimeUsernameProblemLanguageResultExecution timeMemory
1093740_8_8_Reconstruction Project (JOI22_reconstruction)C++17
7 / 100
4526 ms57856 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e6 + 12, MOD = (int)1e9 + 3; #define int ll int n, m, vis[N], timer = 0, p[N], f[N]; vector<array<int, 3>> e(N); vector<vector<int>> tr; vector<int> cur; int id(int v, int u) { vector<vector<pair<int,int>>> g(n + 1); for(int i:cur) { g[e[i][1]].push_back({e[i][2], i}); g[e[i][2]].push_back({e[i][1], i}); } queue<int> q; q.push(v); ++timer; vis[v] = timer; while(!q.empty()) { int x = q.front(); q.pop(); // cout << x << ' ' << p[x] << '\n'; for(auto [to, i]:g[x]) { // cout << to << "x\n"; if(vis[to] != timer) { vis[to] = timer; p[to] = x; f[to] = i; q.push(to); } } } int ret = 1e9; while(u != v) { ret = min(ret, f[u]); u = p[u]; // cerr << u << ' ' << v << '\n'; } return ret; } int P[N]; int get(int a) { if(P[a] == a) return a; return P[a] = get(P[a]); } bool merge(int a, int b) { a = get(a); b = get(b); if(a == b) return false; P[a] = b; return true; } ll cost(vector<int> &x, int val) { // cout << (int)x.size() << '\n'; ll ret = 0; for(int i:x) { ret += abs(val - e[i][0]); } return ret; } int l[N], r[N]; const int inf = (int)1e9; void test() { cin >> n >> m; for(int i = 0;i < m; i++) { cin >> e[i][1] >> e[i][2] >> e[i][0]; l[i] = 0, r[i] = inf; } iota(P + 1, P + n + 1, 1); sort(e.begin(), e.begin() + m); int lst = 0; for(int i = 0;i < m; i++) { if(merge(e[i][2], e[i][1])) { cur.push_back(i); continue; } int j = id(e[i][1], e[i][2]); ll val = (e[i][0] + e[j][0] + 1) / 2; l[i] = val; r[j] = val - 1; for(int k = 0; k < (int)cur.size(); k++) { if(cur[k] == j) { cur.erase(cur.begin() + k); break; } } cur.push_back(i); } vector<array<int, 3>> o; for(int i = 0; i < m; i++) { o.push_back({l[i], r[i], e[i][0]}); } sort(o.begin(), o.end()); multiset<int> L, R; multiset<pair<int, int>> st; ll _l = 0, _r = 0; int q; cin >> q; int it = 0; while(q--) { int x; cin >> x; ll res = 0; auto add = [&](int val) { if(val <= x) { _l += val; L.insert(val); } else { _r += val; R.insert(val); } }; auto del = [&](int val) { if(L.find(val) != L.end()) { L.erase(L.find(val)); _l -= val; } else { R.erase(R.find(val)); _r -= val; } }; auto f = [&](multiset<int> &t, ll s) { res += abs(s - x * 1ll * (int)t.size()); }; while(it < m && o[it][0] <= x) { st.insert({o[it][1], o[it][2]}); add(o[it][2]); it++; } while(!st.empty()) { auto [d, e] = (*st.begin()); if(d < x) { del(e); st.erase({d,e}); } else { break; } } while(!R.empty()) { int val = (*R.begin()); // cerr << val << ' ' << x << '\n'; if(val <= x) { R.erase(R.find(val)); _r -= val; add(val); } else { break; } } f(L, _l); f(R, _r); cout << res << '\n'; } } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); int t = 1; // cin >> t; while(t--) test(); return 0; }

Compilation message (stderr)

reconstruction.cpp: In function 'void test()':
reconstruction.cpp:75:9: warning: unused variable 'lst' [-Wunused-variable]
   75 |     int lst = 0;
      |         ^~~
#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...