제출 #1073862

#제출 시각아이디문제언어결과실행 시간메모리
1073862awuReconstruction Project (JOI22_reconstruction)C++14
100 / 100
4909 ms114368 KiB
#include <bits/extc++.h> using namespace std; using namespace __gnu_pbds; #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2") // #define int long long #define ll long long #define f first #define s second #define all(x) x.begin(), x.end() #define debug(x) [](decltype(x) _x){cerr << #x << " = " << _x << endl; return _x;}(x); using pii = pair<int, int>; const int inf = 1 << 30; ll pc = 0; ll pl; ll now() { return chrono::system_clock().now().time_since_epoch().count(); } void pstart() { pl = now(); } void pend() { pc += now() - pl; } struct dsu { short p[500]; dsu(int n) { for(int i = 0; i < 500; i++) { p[i] = -1; } } int find(int x) { return p[x] < 0 ? x : p[x] = find(p[x]); } void merge(int x, int y) { x = find(x); y = find(y); if(x == y) return; if(p[x] < p[y]) swap(x, y); p[y] += p[x]; p[x] = y; } }; struct my_hash { size_t operator()(int x) const { return x * 31; } }; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); // ll start = now(); int n, m; cin >> n >> m; struct edge { short a, b; int w; }; vector<edge> el(m); for(int i = 0; i < m; i++) { cin >> el[i].a >> el[i].b >> el[i].w; el[i].a--; el[i].b--; } sort(all(el), [&](edge a, edge b) { return a.w < b.w; }); int q; cin >> q; vector<int> x(q); for(int i = 0; i < q; i++) { cin >> x[i]; } auto sx = x; sort(all(sx)); gp_hash_table<int, ll, my_hash> ans; int cnt = 0; function<void(int, int, vector<int>)> dnc = [&](int ql, int qr, vector<int> es) { if(ql == qr) return; if(es.size() == n - 1) { cnt += qr - ql; for(int i = ql; i < qr; i++) { ll tot = 0; for(auto j : es) { tot += abs(el[j].w - sx[i]); } ans[sx[i]] = tot; } return; } int qm = (ql + qr) / 2; int qw = sx[qm]; // debug(qw); // if(qw == 8) { // for(auto e : el) { // cerr << e.a << " " << e.b << " " << e.w << endl; // } // cerr << endl; // } int loc = 0, eqc = 0, hic = 0; for(auto i : es) { if(el[i].w < qw) loc++; else if(el[i].w > qw) hic++; } vector<int> lo(es.begin(), es.begin() + loc), eq(es.begin() + loc, es.end() - hic), hi(es.end() - hic, es.end()); reverse(all(lo)); int ls = lo.size(), hs = hi.size(); vector<int> lou, equ, hiu; lou.reserve(128); equ.reserve(128); hiu.reserve(128); dsu uf(n); int ec = 0; for(auto i : eq) { if(uf.find(el[i].a) != uf.find(el[i].b)) { uf.merge(el[i].a, el[i].b); equ.push_back(i); ec++; } } int loi = 0, hii = 0; ll tot = 0; while(ec < n - 1) { bool dlo = false; if(hii == hi.size()) dlo = true; else if(loi == lo.size()) dlo = false; else dlo = qw - el[lo[loi]].w < el[hi[hii]].w - qw; if(dlo) { int i = lo[loi]; loi++; if(uf.find(el[i].a) != uf.find(el[i].b)) { uf.merge(el[i].a, el[i].b); // pstart(); lou.push_back(i); // pend(); tot += qw - el[i].w; ec++; } } else { int i = hi[hii]; hii++; if(uf.find(el[i].a) != uf.find(el[i].b)) { uf.merge(el[i].a, el[i].b); // pstart(); hiu.push_back(i); // pend(); tot += el[i].w - qw; ec++; } } } ans[qw] = tot; reverse(all(lo)); reverse(all(hi)); lo.reserve(lo.size() + equ.size() + hiu.size()); hi.reserve(hi.size() + equ.size() + lou.size()); for(auto i : equ) { lo.push_back(i); hi.push_back(i); // if(qw == 8) cerr << i.a << " " << i.b << " " << i.w << endl; } for(auto i : lou) { hi.push_back(i); // if(qw == 8) cerr << i.a << " " << i.b << " " << i.w << endl; } for(auto i : hiu) { lo.push_back(i); // if(qw == 8) cerr << i.a << " " << i.b << " " << i.w << endl; } reverse(all(hi)); dnc(ql, qm, move(lo)); dnc(qm + 1, qr, move(hi)); // dnc(ql, qm, el); // dnc(qm + 1, qr, el); }; vector<int> id(m); iota(all(id), 0); dnc(0, q, id); for(auto i : x) { cout << ans[i] << "\n"; } // ll end = now(); // debug((double)pc / (end - start)); // debug(cnt); }

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

reconstruction.cpp: In lambda function:
reconstruction.cpp:84:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   84 |     if(es.size() == n - 1) {
      |        ~~~~~~~~~~^~~~~~~~
reconstruction.cpp:129:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |       if(hii == hi.size()) dlo = true;
      |          ~~~~^~~~~~~~~~~~
reconstruction.cpp:130:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |       else if(loi == lo.size()) dlo = false;
      |               ~~~~^~~~~~~~~~~~
reconstruction.cpp:104:18: warning: unused variable 'eqc' [-Wunused-variable]
  104 |     int loc = 0, eqc = 0, hic = 0;
      |                  ^~~
reconstruction.cpp:111:9: warning: unused variable 'ls' [-Wunused-variable]
  111 |     int ls = lo.size(), hs = hi.size();
      |         ^~
reconstruction.cpp:111:25: warning: unused variable 'hs' [-Wunused-variable]
  111 |     int ls = lo.size(), hs = hi.size();
      |                         ^~
#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...