Submission #1119168

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119168		Master	Reconstruction Project (JOI22_reconstruction)	C++17	7 / 100	2144 ms	268620 KiB

reconstruction

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(lmao) lmao.begin(), lmao.end()

using namespace std;

typedef pair<ll, ll> pii;

const int N = 1e6 + 5;
const int M = 1e6 + 5;

struct _edge{
  int a, b, c;
} h[N];

int n, m, q, W[M];

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(h[i].c - W[k]), h[i].a, h[i].b});
      }
      sort(all(edge));
      for(auto [val, x, y] : edge){
        if(dsu(x, y)) ans += val;
      }
      cout << ans << "\n";
    }
  }
}

int nxt[N], wt[N], sz[N], pa[N], cnt, demin, in[N], en[N];
bool flag[N];
vector<int> edge;
vector<pair<int,int>> p[N];

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

void dsu(int x,int y){
  x = fin(x);
  y = fin(y);
  if(x == y) return;
  if(sz[x] < sz[y]) swap(x, y);
  sz[x] += sz[y];
  pa[y] = x;
}

void dfs(int u,int v){
  in[u] = ++demin;
//  cerr << u << " " << v << " s\n";
  for(auto [j, w] : p[u]) if(j != v) {
    nxt[j] = u;
    wt[j] = w;
    dfs(j, u);
  }
  en[u] = ++demin;
}

bool kt(int u, int v){
  return in[u] <= in[v] && in[v] <= en[u];
}

void reset(){
  for(int i = 1; i <= n; i ++){
    in[i] = en[i] = wt[i] = nxt[i] = 0, pa[i] = i, sz[i] = 1;
    p[i].clear();
  }
  demin = 0;
}

vector<tuple<int,int,int>> imp;
vector<int> rrh, weight, Q[N];
vector<pair<int,int>> change[N];
int kq[M];

ll bit[N], T[N];
int sze;

int add(int i,int val,int x){
  for(; i <= sze; i += i & -i) bit[i] += val, T[i] += x;
}

pair<ll,ll> get(int i){
  int cnt = 0, ret = 0;
  for(;i > 0; i -= i & -i){
    cnt += bit[i];
    ret += T[i];
  }
  return {cnt, ret};
}

signed main(){
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  #define task "v"
  if(fopen(task ".inp","r")){
    freopen(task ".inp","r",stdin);
    freopen(task ".out","w",stdout);
  }

  cin >> n >> m;
  for(int i = 1; i <= m; i ++){
    cin >> h[i].a >> h[i].b >> h[i].c;
    weight.push_back(h[i].c);
  }

  sort(all(weight)); weight.resize(unique(all(weight)) - weight.begin());
  sze = (int)weight.size();

  cin >> q;
  for(int i = 1; i <= q; i ++) cin >> W[i];

  if(q <= 10) {
    sub2 :: solve();
    return 0;
  }

  sort(h + 1, h + m + 1, [&](_edge x, _edge y){return x.c < y.c;});

//  for(int i = 1; i <= m; i ++) cerr << h[i].a << " " << h[i].b << " " << h[i].c << " \n";

  reset();
  bool ff = true;

  /*
  4 5 2
  1 5 3
  1 4 5
  3 4 6
  3 5 6
  2 3 7
  1 2 8
  1 5 11
  1 3 13
  2 4 15
  */


  for(int i = 1; i <= m; i ++){
    int x = h[i].a, y = h[i].b, w = h[i].c;
//    cerr << i << " " << " " << x << " " << y << " " << w << " h\n";
    if(ff == false || fin(x) == fin(y)){
      reset();
      vector<int> new_edge;
      for(auto j : edge) if(flag[j]) {
//        cerr << h[j].a << " " << h[j].b << " e\n";
        p[h[j].a].push_back({h[j].b, j});
        p[h[j].b].push_back({h[j].a, j});
      }
      for(int i = 1; i <= n; i ++) if(!in[i]) dfs(i, 0);
      int mi = m + 1, px = x, py = y;
      while(!kt(px, y)){
        mi = min(mi, wt[px]);
        px = nxt[px];
      }
      while(!kt(py, x)){
        mi = min(mi, wt[py]);
        py = nxt[py];
      }
      int mid = (w + h[mi].c) / 2 + 1;
      imp.push_back({mid, h[mi].c, w});
      rrh.push_back(mid);
      flag[mi] = 0;
      flag[i] = 1;
      for(auto j : edge) if(flag[j]) {
        new_edge.push_back(j);
        dsu(h[j].a, h[j].b);
      }
      swap(new_edge, edge);
      edge.push_back(i);
      dsu(h[i].a, h[i].b);
    }else{
      dsu(x, y);
      flag[i] = 1;
      edge.push_back(i);
      cnt++;
      if(cnt == n - 1) ff = false;
    }
  }


  sort(all(rrh)); rrh.resize(unique(all(rrh)) - rrh.begin());
  for(auto [w, x, y] : imp) {
    int pos = lower_bound(all(rrh), w) - rrh.begin() + 1;
    change[pos].push_back({x, y});
  }
  for(int i = 1; i <= q; i ++){
    int pos = upper_bound(all(rrh), W[i]) - rrh.begin();
    Q[pos].push_back(i);
  }
  reset();
  for(int i = 1; i <= m; i ++) {
    int x = h[i].a, y = h[i].b, w = h[i].c;
    if(fin(x) != fin(y)) {
      dsu(x, y);
      int pw = lower_bound(all(weight), w) - weight.begin() + 1;
      add(pw, 1, w);
    }
  }

  for(int k = 0; k <= (int)rrh.size(); k ++) {
    for(auto [x, y] : change[k]) {
      int px = lower_bound(all(weight), x) - weight.begin() + 1;
      int py = lower_bound(all(weight), y) - weight.begin() + 1;
      add(px, -1, -x);
      add(py, 1, y);
    }
    for(auto i : Q[k]) {
      int pos = upper_bound(all(weight), W[i]) - weight.begin();
      auto le = get(pos);
      auto ri = get(sze);
      ri = {ri.first - le.first, ri.second - le.second};
      kq[i] = 1ll * le.first * W[i] - le.second + ri.second - 1ll * ri.first * W[i];
    }
  }

  for(int i = 1; i <= q; i ++) cout << kq[i] << "\n";
}

Compilation message (stderr)

reconstruction.cpp: In function 'long long int add(long long int, long long int, long long int)':
reconstruction.cpp:104:1: warning: no return statement in function returning non-void [-Wreturn-type]
  104 | }
      | ^
reconstruction.cpp: In function 'int main()':
reconstruction.cpp:120:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |     freopen(task ".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:121:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |     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