Submission #575125

#TimeUsernameProblemLanguageResultExecution timeMemory
575125SortingReconstruction Project (JOI22_reconstruction)C++17
42 / 100
5095 ms400504 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; template<class T> void check_min(T &a, const T &b){ a = (a < b) ? a : b; } template<class T> void check_max(T &a, const T &b){ a = (a > b) ? a : b; } #define all(x) (x).begin(), (x).end() const int N = 500 + 3; const int M = 1e5 + 3; const int Q = 1e6 + 3; const int INF = 1e9; int n, m, q; array<ll, 3> e[M]; ll x[Q]; struct DSU{ int sz[N], par[N]; void init(int n){ for(int i = 1; i <= n; ++i) sz[i] = 1, par[i] = i; } int getP(int x){ if(par[x] == x) return x; return par[x] = getP(par[x]); } bool unite(int a, int b){ a = getP(a), b = getP(b); if(a == b) return false; if(sz[a] < sz[b]) swap(a, b); sz[a] += sz[b]; par[b] = a; return true; } } dsu; int pr[M][N], su[M][N]; int pr_cnt[M], su_cnt[M]; inline void try_dsu(DSU &dsu, int cost, int idx, ll &ans, int &cnt){ if(dsu.unite(e[idx][1], e[idx][2])){ ans += cost; ++cnt; } } ll get_ans(int *e1, int *e2, ll x, int ptr){ ll ans = 0; int e1_sz = (ptr >= 1) ? pr_cnt[ptr - 1] : 0; int e2_sz = (ptr <= m - 1) ? su_cnt[ptr] : 0; dsu.init(n); int ptr1 = 0, ptr2 = 0, cnt = 0; while(ptr1 != e1_sz && ptr2 != e2_sz && cnt < n - 1){ int cost1 = x - e[e1[ptr1]][0]; int cost2 = e[e2[ptr2]][0] - x; if(cost1 < cost2) try_dsu(dsu, cost1, e1[ptr1++], ans, cnt); else try_dsu(dsu, cost2, e2[ptr2++], ans, cnt); } while(ptr1 != e1_sz && cnt < n - 1){ int cost1 = x - e[e1[ptr1]][0]; try_dsu(dsu, cost1, e1[ptr1++], ans, cnt); } while(ptr2 != e2_sz && cnt < n - 1){ int cost2 = e[e2[ptr2]][0] - x; try_dsu(dsu, cost2, e2[ptr2++], ans, cnt); } return ans; } int main(){ ios::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m; for(int i = 0; i < m; ++i){ cin >> e[i][1] >> e[i][2] >> e[i][0]; } sort(e, e + m); pr[0][0] = 0; pr_cnt[0] = 1; for(int i = 1; i < m; ++i){ dsu.init(n); pr[i][pr_cnt[i]++] = i; for(int j = 0; j < pr_cnt[i - 1]; ++j){ int idx = pr[i - 1][j]; if(dsu.unite(e[idx][1], e[idx][2])) pr[i][pr_cnt[i]++] = idx; } } su[m - 1][0] = m - 1; su_cnt[m - 1] = 1; for(int i = m - 2; i >= 0; --i){ dsu.init(n); su[i][su_cnt[i]++] = i; for(int j = 0; j < su_cnt[i + 1]; ++j){ int idx = su[i + 1][j]; if(dsu.unite(e[idx][1], e[idx][2])) su[i][su_cnt[i]++] = idx; } } int ptr = 0; cin >> q; for(int i = 0; i < q; ++i){ cin >> x[i]; while(ptr != m && x[i] >= e[ptr][0]) ++ptr; int *e1; if(0 <= ptr - 1){ e1 = pr[ptr - 1]; } int *e2; if(ptr <= m - 1){ e2 = su[ptr]; } auto ans = get_ans(e1, e2, x[i], ptr); cout << ans << "\n"; } }

Compilation message (stderr)

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:134:27: warning: 'e2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  134 |         auto ans = get_ans(e1, e2, x[i], ptr);
      |                    ~~~~~~~^~~~~~~~~~~~~~~~~~~
reconstruction.cpp:134:27: warning: 'e1' may be used uninitialized in this function [-Wmaybe-uninitialized]
#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...