Submission #888476

#	Time	Username	Problem	Language	Result	Execution time	Memory
888476		nguyentunglam	Reconstruction Project (JOI22_reconstruction)	C++17	100 / 100	1838 ms	32852 KiB

reconstruction

#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define endl "\n"
#define int long long
using namespace std;

const int N = 510, M = 1e5 + 10;

int lab[N], p[N];

int n, m, q;

int x[M], y[M], w[M];

bool in[M];

int root(int v) {
  return lab[v] < 0 ? v : lab[v] = root(lab[v]);
}

void join(int u, int v) {
  u = root(u); v = root(v);
  if (u == v) return;
  if (lab[u] > lab[v]) swap(u, v);
  lab[u] += lab[v];
  lab[v] = u;
}

tuple<int, int, int> e[M];

int32_t main() {
  #define task ""

  cin.tie(0) -> sync_with_stdio(0);

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

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

  cin >> n >> m;

  vector<tuple<int, int, int> > e;

  for(int i = 1; i <= m; i++) {
    int a, b, c; cin >> a >> b >> c;
    e.emplace_back(c, a, b);
  }

  sort(all(e));

  for(int i = 1; i <= m; i++) tie(w[i], x[i], y[i]) = e[i - 1];

  for(int i = 1; i <= n; i++) p[i] = m;

  vector<tuple<int, int, int> > event;

//  for(int i = 1; i <= m; i++) cout << x[i] << " " << y[i] << " " << w[i] << endl;
  #define ii pair<int, int>
  priority_queue<ii, vector<ii>, greater<ii> > Q;

  long long sum = 0;

  int cnt = 0;

  for(int i = m; i >= 1; i--) if (x[i] != y[i]) {
    fill(lab + 1, lab + n + 1, -1);
    p[0] = i;
    int better = 0;
    for(int j = 1; j < n; j++) {
      int k = min(p[j - 1] - 1, p[j]);
      while (k > 0 && root(x[k]) == root(y[k])) k--;
      if (k == 0) break;
      p[j] = k;
      join(x[k], y[k]);
      if (better == 0 && root(x[i]) == root(y[i])) better = k;
    }
    if (!better) {
      in[i] = 1;
      Q.push({w[i], i});
      sum += w[i];
      cnt--;
    }
    else event.emplace_back(w[better] + w[i] + 1 >> 1, better, i);
  }

  sort(all(event));

  cin >> q;

  int j = 0;

  auto calc = [&] (int x) {
    while (!Q.empty() && Q.top().first < x) {
      int j = Q.top().second; Q.pop();
      if (!in[j]) continue;
      sum -= w[j] * 2;
      cnt += 2;
    }
  };

  while (q--) {
    int x; cin >> x;

    while (j < event.size() && x >= get<0> (event[j])) {
      int useless, a, b; tie(useless, a, b) = event[j];
      calc(x);
      in[a] = 0;
      if (w[a] >= x) {
        sum -= w[a];
        cnt++;
      }
      else {
        sum += w[a];
        cnt--;
      }
      in[b] = 1;
      Q.push({w[b], b});
      sum += w[b];
      cnt--;
      j++;
    }
    calc(x);
    cout << sum + 1LL * x * cnt << endl;
  }

}

Compilation message (stderr)

reconstruction.cpp: In function 'int32_t main()':
reconstruction.cpp:89:46: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   89 |     else event.emplace_back(w[better] + w[i] + 1 >> 1, better, i);
      |                             ~~~~~~~~~~~~~~~~~^~~
reconstruction.cpp:110:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::tuple<long long int, long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     while (j < event.size() && x >= get<0> (event[j])) {
      |            ~~^~~~~~~~~~~~~~
reconstruction.cpp:37:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     freopen("task.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:38:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     freopen("task.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:42:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     freopen (task".inp", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:43:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     freopen (task".out", "w", stdout);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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