Submission #1115113

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115113		VinhLuu	Reconstruction Project (JOI22_reconstruction)	C++17	7 / 100	5073 ms	44164 KiB

reconstruction

#include <bits/stdc++.h>
#define all(vin) vin.begin(), vin.end()
#define ll long long
using namespace std;

const int N = 2e5 + 5;

int n, m, q, _x[N], _y[N], _c[N], A[N];

namespace sub4{

  int pa[N], sz[N];
  int fin(int u){
    return pa[u] == u ? u : pa[u] = fin(pa[u]);
  }

  bool dsu(int u,int v){
    u = fin(u);
    v = fin(v);
    if(u == v) return 0;
    if(sz[u] < sz[v]) swap(u, v);
    sz[u] += sz[v];
    pa[v] = u;
    return 1;
  }

  int le[N], ri[N], pt[N];
  ll kq[N];
  vector<int> rrh;

  void solve(){

    for(int i = 1; i <= m; i ++) rrh.push_back(_c[i]);
    sort(all(rrh)); rrh.resize(unique(all(rrh)) - rrh.begin());

    for(int k = 1; k <= (int)rrh.size(); k ++){
      int tmp = rrh[k - 1];
      pt[k] = rrh[k - 1];
      vector<pair<int,int>> edge;
      ll ans = 0;
      for(int i = 1; i <= n; i ++) pa[i] = i, sz[i] = 1;
      for(int i = 1; i <= m; i ++){
         edge.push_back({abs(_c[i] - tmp), i});
      }
      sort(all(edge));
      for(auto [wt, id] : edge){
        if(dsu(_x[id], _y[id])){
          le[k] += (_c[id] <= tmp);
          ri[k] += (_c[id] >= tmp);
          kq[k] += wt;
//          cerr << id << " " << _x[id] << " " << _y[id] << " " << _c[id] << " r\n";
        }
      }
//      cerr << "       " << k << " " << tmp << " " << kq[k] << " " << le[k] << " " << ri[k] << " t\n";
    }
    int ptr = 0, lag = (int)rrh.size();

    for(int k = 1; k <= q; k ++){
      while(ptr < lag && pt[ptr + 1] < A[k]) ptr++;
      if(!ptr){
        int i = ptr + 1;
        cout << kq[i] + 1ll * ri[i] * (pt[i] - A[k]) << "\n";
        continue;
      }
      if(ptr == lag){
        int i = ptr;
        cout << kq[ptr] + 1ll * le[i] * (A[k] - pt[ptr]) << "\n";
        continue;
      }
      ll B = kq[ptr] + 1ll * le[ptr] * (A[k] - pt[ptr]) - 1ll * (n - 1 - le[ptr]) * (A[k] - pt[ptr]);
      ll C = kq[ptr + 1] + 1ll * ri[ptr + 1] * (pt[ptr + 1] - A[k]) - 1ll * (n - 1 - ri[ptr + 1]) * (pt[ptr + 1] - A[k]);
//      cerr << B << " " << C << " r\n";
      cout << min(B, C) << "\n";
    }
  }
}
/*
4 6
1 2 2
2 3 16
3 4 3
3 4 3
2 4 13
1 3 7
5
5 7 8 8 10
*/

namespace sub3{
  vector<int> vr[N];
  ll st[N << 2], lz[N << 2], T[N << 2];

  void dolz(int i){
    if(!lz[i]) return;
    int x = lz[i]; lz[i] = 0;
    lz[i << 1] += x;
    lz[i << 1|1] += x;
    st[i << 1] += x;
    st[i << 1|1] += x;
    T[i << 1] += T[i];
    T[i << 1|1] += T[i];
    T[i] = 0;
  }

  void update(int i,int l,int r,int u,int v,int val,int type){
    if(l > r || r < u || v < l) return;
    if(u <= l && r <= v){
      st[i] += val;
      T[i] += type;
      lz[i] += val;
      return;
    }
    dolz(i);
    int mid = (l + r) / 2;
    update(i << 1, l, mid, u, v, val, type);
    update(i << 1|1, mid + 1, r, u, v, val, type);
  }

  int idx[N];

  int get(int i,int l,int r,int u){
    if(l > r || r < u || u < l) return 0;
    if(l == r){
      idx[u] = i;
      return st[i];
    }
    dolz(i);
    int mid = (l + r) / 2;
    return get(i << 1, l, mid, u) + get(i << 1|1, mid + 1, r, u);
  }

  void solve(){
    sort(A + 1, A + q + 1);
    for(int i = 1; i <= m; i ++){
      vr[_x[i]].push_back(_c[i]);
    }
    for(int i = 1; i < n; i ++){
      sort(all(vr[i]));
      for(int j = 0; j < vr[i].size(); j ++){
        if(!j){
          int pos = upper_bound(A + 1, A + q + 1, vr[i][j] - 1) - A - 1;
          if(pos >= 1){
            update(1, 1, q, 1, pos, vr[i][j], 0);
          }
          continue;
        }
        int pre = vr[i][j - 1];
        int x = vr[i][j];
        int mid = (x + pre) / 2;
        int _right = upper_bound(A + 1, A + q + 1, mid) - A - 1;
        int _left = lower_bound(A + 1, A + q + 1, pre) - A;
        if(_left <= _right) update(1, 1, q, _left, _right, -pre, 1);
        _right = upper_bound(A + 1, A + q + 1, x) - A - 1;
        _left = lower_bound(A + 1, A + q + 1, mid + 1) - A;
        if(_left <= _right) update(1, 1, q, _left, _right, x, 0);
      }
      int pos = lower_bound(A + 1, A + q + 1, vr[i].back() + ((int)vr[i].size() > 1)) - A;
      if(pos <= q){
        update(1, 1, q, pos, q, -vr[i].back(), 1);
      }
    }
    for(int i = 1; i <= q; i ++){
      int val = get(1, 1, q, i);
      int pos = idx[i];
      cout << val + T[pos] * A[i] - (n - 1 - T[pos]) * A[i] << "\n";
    }
  }

}

namespace sub2{
  int pa[N], sz[N];
  int fin(int u){
    return pa[u] == u ? u : pa[u] = fin(pa[u]);
  }

  bool dsu(int u,int v){
    u = fin(u);
    v = fin(v);
    if(u == v) return 0;
    if(sz[u] < sz[v]) swap(u, v);
    sz[u] += sz[v];
    pa[v] = u;
    return 1;
  }

  void solve(){
    for(int k = 1; k <= q; k ++){
      vector<tuple<int,int,int>> edge;
      ll ans = 0;
      for(int i = 1; i <= n; i ++) pa[i] = i, sz[i] = 1;
      for(int i = 1; i <= m; i ++){
         edge.push_back({abs(_c[i] - A[k]), _x[i], _y[i]});
      }
      sort(all(edge));
      for(auto [val, x, y] : edge){
        if(dsu(x, y)) ans += val;
      }
      cout << ans << "\n";
    }
  }
}

namespace sub1{
  #define int long long
  bool flag[N];
  vector<int> p[N];
  void solve(){
    for(int k = 1; k <= q; k ++){
      int ans = 1e18;
      for(int msk = 0; msk < (1 << m); msk ++){
        for(int i = 1; i <= n; i ++){
          flag[i] = 0;
          p[i].clear();
        }
        int cnt = 0;
        for(int i = 1; i <= m; i ++) if(msk >> (i - 1) & 1){
          int x = _x[i];
          int y = _y[i];
          p[x].push_back(y);
          p[y].push_back(x);
          cnt += abs(_c[i] - A[k]);
        }
        queue<int> q;
        q.push(1);
        flag[1] = 1;
        while(!q.empty()){
          int u = q.front(); q.pop();
          for(auto j : p[u]) if(!flag[j]){
            q.push(j);
            flag[j] = 1;
          }
        }
        bool ff = true;
        for(int i = 1; i <= n; i ++) if(!flag[i]){
          ff = false;
          break;
        }
        if(ff) ans = min(ans, cnt);
      }
      cout << ans << "\n";
    }

  }
}

signed main(){
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define task "repj"
  if(fopen(task ".inp","r")){
    freopen(task ".inp","r",stdin);
    freopen(task ".out","w",stdout);
  }

  cin >> n >> m;
  bool ff = true;
  for(int i = 1; i <= m; i ++){
    cin >> _x[i] >> _y[i] >> _c[i];
    if(_y[i] != _x[i] + 1) ff = false;
  }
  cin >> q;
  for(int i = 1; i <= q; i ++) cin >> A[i];

  if(m <= 16 && q <= 10) sub1 :: solve();
  else if(q <= 10) sub2 :: solve();
  else if(ff) sub3 :: solve();
  else sub4 :: solve();
}

Compilation message (stderr)

reconstruction.cpp: In function 'void sub4::solve()':
reconstruction.cpp:40:10: warning: unused variable 'ans' [-Wunused-variable]
   40 |       ll ans = 0;
      |          ^~~
reconstruction.cpp: In function 'void sub3::solve()':
reconstruction.cpp:139:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |       for(int j = 0; j < vr[i].size(); j ++){
      |                      ~~^~~~~~~~~~~~~~
reconstruction.cpp: In function 'int main()':
reconstruction.cpp:251:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  251 |     freopen(task ".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:252:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  252 |     freopen(task ".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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