제출 #772477

#제출 시각아이디문제언어결과실행 시간메모리
772477minhcoolReconstruction Project (JOI22_reconstruction)C++17
35 / 100
3634 ms79908 KiB
#define local #ifndef local #include "" #endif #include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; using namespace std; #define int long long #define fi first #define se second #define pb push_back #define mp make_pair typedef pair<int, int> ii; typedef pair<ii, int> iii; typedef pair<ii, ii> iiii; const int N = 2e6 + 5; const int oo = 1e18 + 7, mod = 1e9 + 7; mt19937 rng(1); int rnd(int l, int r){ int temp = rng() % (r - l + 1); return abs(temp) + l; } int n, m; int le[N], ri[N]; vector<iii> edge; vector<int> diffs; bool cmp(iii a, iii b){ return a.se < b.se; } vector<iii> cur_mst; int rt[N], sz[N]; int root(int x){ return (x == rt[x] ? x : rt[x] = root(rt[x])); } bool merge(int x, int y){ x = root(x), y = root(y); if(x == y) return 0; if(sz[x] < sz[y]) swap(x, y); sz[x] += sz[y]; rt[y] = x; return 1; } vector<ii> updates[N]; #ifdef local void process(){ cin >> n >> m; for(int i = 1; i <= m; i++){ int x, y, w; cin >> x >> y >> w; edge.pb({{x, y}, w}); } sort(edge.begin(), edge.end(), cmp); for(int i = 0; i < m; i++) le[i] = ri[i] = -oo; for(int i = 1; i < edge.size(); i++){ cur_mst.pb({edge[i - 1].fi, i - 1}); iii it = edge[i]; for(int j = 1; j <= n; j++){ rt[j] = j, sz[j] = 1; } vector<iii> nw; for(int j = cur_mst.size() - 1; j >= 0; j--){ if(merge(cur_mst[j].fi.fi, cur_mst[j].fi.se)){ nw.pb(cur_mst[j]); if(root(it.fi.fi) == root(it.fi.se) && le[i] < 0) le[i] = cur_mst[j].se; } } reverse(nw.begin(), nw.end()); cur_mst = nw; } cur_mst.clear(); for(int i = (int)edge.size() - 2; i >= 0; i--){ cur_mst.pb({edge[i + 1].fi, i + 1}); iii it = edge[i]; for(int j = 1; j <= n; j++){ rt[j] = j, sz[j] = 1; } vector<iii> nw; for(int j = cur_mst.size() - 1; j >= 0; j--){ if(merge(cur_mst[j].fi.fi, cur_mst[j].fi.se)){ nw.pb(cur_mst[j]); if(root(it.fi.fi) == root(it.fi.se) && ri[i] < 0) ri[i] = cur_mst[j].se; } } reverse(nw.begin(), nw.end()); cur_mst = nw; // cout << "OK " << i << "\n"; // for(auto it : cur_mst) cout << it.fi.fi << " " << it.fi.se << " " << it.se << "\n"; } for(int i = 0; i < m; i++){ int temp1 = (le[i] < 0 ? 0 : (edge[le[i]].se + edge[i].se + 2) / 2); int temp2 = (ri[i] < 0 ? 2e9 : (edge[i].se + edge[ri[i]].se) / 2); // cout << i << " " << le[i] << " " << ri[i] << " " << temp1 << " " << temp2 << "\n"; diffs.pb(temp1); diffs.pb(temp2 + 1); } sort(diffs.begin(), diffs.end()); diffs.resize(unique(diffs.begin(), diffs.end()) - diffs.begin()); for(int i = 0; i < m; i++){ int temp1 = (le[i] < 0 ? 0 : (edge[le[i]].se + edge[i].se + 2) / 2); int temp2 = (ri[i] < 0 ? 2e9 : (edge[i].se + edge[ri[i]].se) / 2); int pos1 = lower_bound(diffs.begin(), diffs.end(), temp1) - diffs.begin(); int pos2 = lower_bound(diffs.begin(), diffs.end(), temp2) - diffs.begin(); updates[pos1].pb({i, 1}); updates[pos2].pb({i, -1}); //diffs.pb(temp1); //diffs.pb(temp2 + 1); } multiset<int> mls; int q; cin >> q; int itr = 0; while(q--){ int x; cin >> x; while(itr < diffs.size() && diffs[itr] <= x){ for(auto it : updates[itr]){ // cout << edge[it.fi].se << " " << it.se << "\n"; if(it.se > 0) mls.insert(edge[it.fi].se); else mls.erase(mls.find(edge[it.fi].se)); } itr++; } int total = 0, mx = 0; //for(auto it : mls) cout << it << " "; // cout << "\n"; for(auto it : mls){ total += abs(it - x); mx = max(mx, it - x); } if(mls.size() != (n - 1)) total += (n - 1 - mls.size()) * mx; cout << total << "\n"; } //for(int i = 0; i < } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); process(); } #endif

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

reconstruction.cpp: In function 'void process()':
reconstruction.cpp:72:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |  for(int i = 1; i < edge.size(); i++){
      |                 ~~^~~~~~~~~~~~~
reconstruction.cpp:133:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |   while(itr < diffs.size() && diffs[itr] <= x){
      |         ~~~~^~~~~~~~~~~~~~
reconstruction.cpp:148:17: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  148 |   if(mls.size() != (n - 1)) total += (n - 1 - mls.size()) * mx;
      |      ~~~~~~~~~~~^~~~~~~~~~
#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...