Submission #888446

#	Time	Username	Problem	Language	Result	Execution time	Memory
888446		nguyentunglam	Reconstruction Project (JOI22_reconstruction)	C++17	31 / 100	5066 ms	25516 KiB

reconstruction

#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define endl "\n"
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;

  long long cur = 0;

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

//  for(int i = 1; i <= m; i++) cout << x[i] << " " << y[i] << " " << w[i] << endl;

  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) cur += w[i], in[i] = 1;
    else event.emplace_back(w[better] + w[i] + 1 >> 1, better, i);
  }

  sort(all(event));

  cin >> q;

  int j = 0;

  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];
      in[a] = 0;
      in[b] = 1;
      j++;
    }
    long long ans = 0;
    for(int i = 1; i <= m; i++) if (in[i]) ans += abs(x - w[i]);
    cout << ans << endl;
  }

}

Compilation message (stderr)

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

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