Submission #859704

#	Time	Username	Problem	Language	Result	Execution time	Memory
859704		nguyentunglam	Reconstruction Project (JOI22_reconstruction)	C++17	3 / 100	5069 ms	18828 KiB

reconstruction

#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
using namespace std;
const int N = 1e5 + 01;
int a[N], b[N], w[N], lab[N], x[N];
int n, m;

vector<int> use[N];

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

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

bool check(int cost, int idx) {
   for(int i = 1; i <= n; i++) lab[i] = -1;

   for(int i = 1; i <= m; i++) if (i != idx) {
//      cout << abs(cost - w[i]) << " " << abs(cost - w[idx]) << endl;
      if (make_pair(abs(cost - w[i]), i) < make_pair(abs(cost - w[idx]), idx)) {
         join(a[i], b[i]);
      }
   }

   return root(a[idx]) != root(b[idx]);
}

int 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> > edge;

   for(int i = 1; i <= m; i++) {
      int u, v, cost; cin >> u >> v >> cost;
      edge.emplace_back(cost, u, v);
   }

   int q; cin >> q;

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

   sort(edge.begin(), edge.end());

   for(int i = 1; i <= m; i++) tie(w[i], a[i], b[i]) = edge[i - 1];

   for(int i = 1; i <= m; i++) {
      int l = 1e9, r = 0;
      for(int j = 1; j <= q; j++) if (check(x[j], i)) {
         l = min(l, j);
         r = max(r, j);
      }
      for(int j = l; j <= r; j++) use[j].push_back(i);
   }

   for(int i = 1; i <= q; i++) {
      long long ans = 0;
      for(int &j : use[i]) ans += abs(x[i] - w[j]);
      cout << ans << endl;
   }
}

Compilation message (stderr)

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:43:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         freopen ("task.inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:44:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         freopen ("task.out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:47:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         freopen (task".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:48:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         freopen (task".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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