Submission #1167395

#TimeUsernameProblemLanguageResultExecution timeMemory
1167395zNatsumiReconstruction Project (JOI22_reconstruction)C++20
14 / 100
1591 ms83084 KiB
#include <bits/stdc++.h> using namespace std; //#define int long long using ii = pair<int, int>; using tp = tuple<int, int, int>; const int N = 1e6 + 5; const long long INF = 1e9; int n, m, q, que[N]; vector<ii> ad[N]; struct DSU{ int pa[N], sz[N]; void mset(int n){ for(int i = 1; i <= n; i++) pa[i] = i, sz[i] = 1; } int fset(int i){ return i == pa[i] ? i : pa[i] = fset(pa[i]); } bool uset(int u, int v){ u = fset(u), v = fset(v); if(u == v) return false; if(sz[u] < sz[v]) swap(u, v); pa[v] = u; sz[u] += sz[v]; return true; } }; namespace sub12{ DSU d; vector<tp> edge; void solve(){ for(int u = 1; u <= n; u++) for(auto [v, w] : ad[u]) edge.emplace_back(u, v, w); for(int t = 1; t <= q; t++){ sort(edge.begin(), edge.end(), [&](tp x, tp y){ int a = get<2>(x), b = get<2>(y); return abs(a - que[t]) < abs(b - que[t]); }); d.mset(n); long long res = 0; for(auto [u, v, w] : edge) if(d.uset(u, v)) res += 1LL*abs(w - que[t]); cout << res << "\n"; } } } namespace sub3{ vector<int> weight[N]; int ptr[N]; long long res[N]; vector<ii> query; void solve(){ for(int i = 1; i < n; i++){ for(auto [j, w] : ad[i]) if(j == i + 1) weight[i].push_back(w); sort(weight[i].begin(), weight[i].end()); } for(int i = 1; i <= q; i++) query.emplace_back(que[i], i); sort(query.begin(), query.end()); for(auto [x, id] : query){ for(int i = 1; i < n; i++){ while(ptr[i] + 1 < weight[i].size() && weight[i][ptr[i] + 1] <= x) ptr[i]++; int tmp = abs(x - weight[i][ptr[i]]); if(x >= weight[i][ptr[i]] && ptr[i] + 1 < weight[i].size()) tmp = min(tmp, abs(x - weight[i][ptr[i] + 1])); res[id] += tmp; } } for(int i = 1; i <= q; i++) cout << res[i] << "\n"; } } int32_t main(){ cin.tie(0)->sync_with_stdio(0); // #define task "test" // if(fopen(task ".inp", "r")){ // freopen(task ".inp", "r", stdin); // freopen(task ".out", "w", stdout); // } cin >> n >> m; for(int i = 1; i <= m; i++){ int u, v, w; cin >> u >> v >> w; ad[u].emplace_back(v, w); ad[v].emplace_back(u, w); } cin >> q; for(int i = 1; i <= q; i++) cin >> que[i]; if(q <= 10) sub12::solve(); else sub3::solve(); return 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...