제출 #1073862

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1073862		awu	Reconstruction Project (JOI22_reconstruction)	C++14	100 / 100	4909 ms	114368 KiB

reconstruction

#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();
      |                         ^~

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 7 / 7
• Subtask 4: 28 / 28
• Subtask 5: 35 / 35
• Subtask 6: 23 / 23