Submission #1093590

#TimeUsernameProblemLanguageResultExecution timeMemory
1093590_8_8_Reconstruction Project (JOI22_reconstruction)C++17
0 / 100
5097 ms212704 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e6 + 12, MOD = (int)1e9 + 3; 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; } void test() { cin >> n >> m; for(int i = 0;i < m; i++) { cin >> e[i][1] >> e[i][2] >> e[i][0]; } 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][1], e[i][2])) { cur.push_back(i); lst = i; } } tr.push_back(cur); for(int i = 0; i < m; i++) { bool bad = 0; for(int j:cur) { if(j == i) bad = 1; } if(bad) continue; int j = id(e[i][1], e[i][2]); // return; int k = -1; for(int _ = 0; _ < (int)cur.size(); _++) { if(cur[_] == j) { k = _; break; } } cur.erase(cur.begin() + k); cur.push_back(i); tr.push_back(cur); // for(int j:cur) { // cerr << j << ' ' << e[j][1] << ' ' << e[j][2] << '\n'; // } // cout << i << ' ' << j << '\n'; // cout << '\n'; } int q; cin >> q; while(q--) { int x; cin >> x; ll res = cost(tr[0], x); for(auto c:tr) { res = min(res, cost(c, x)); } cout << res << '\n'; } } int 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:71:9: warning: variable 'lst' set but not used [-Wunused-but-set-variable]
   71 |     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...