Submission #1060933

#TimeUsernameProblemLanguageResultExecution timeMemory
1060933sleepntsheepReconstruction Project (JOI22_reconstruction)C++17
3 / 100
5084 ms16624 KiB
#include <iostream> #include <cstring> #include <vector> #include <algorithm> #include <array> using namespace std; using ll = long long; template <typename T, int sz> using ar = array<T, sz>; const int N = 505, M = 1010; int n, m, q, ds[N]; ll mst; ar<int, 3> e[M]; int ds_find(int i) { return (ds[i] < 0) ? i : (ds[i] = ds_find(ds[i])); } void ds_unite(int i, int j, int w) { i = ds_find(i); j = ds_find(j); if (i == j) return; mst += w; if (-ds[i] > -ds[j]) swap(i, j); ds[j] += ds[i]; ds[i] = j; } int main() { scanf("%d%d", &n, &m); for (int i = 0; i < m; ++i) scanf("%d%d%d", &e[i][1], &e[i][2], &e[i][0]); sort(e, e+m); scanf("%d", &q); for (int x, i = 0; i < q; ++i) { scanf("%d", &x); memset(ds, -1, sizeof * ds * (n + 1)); mst = 0; int pl, pr; pr = lower_bound(e, e + m, ar<int, 3>{x, -1, -1}) - e; pl = pr - 1; while (pl >= 0 or pr < m) { if (pl == -1 or pr < m and e[pr][0] - x < x - e[pl][0]) ds_unite(e[pr][1], e[pr][2], e[pr][0] - x), ++pr; else ds_unite(e[pl][1], e[pl][2], x - e[pl][0]), --pl; } printf("%lld\n", mst); } }

Compilation message (stderr)

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:51:36: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   51 |             if (pl == -1 or pr < m and e[pr][0] - x < x - e[pl][0])
reconstruction.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
reconstruction.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         scanf("%d%d%d", &e[i][1], &e[i][2], &e[i][0]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
reconstruction.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         scanf("%d", &x);
      |         ~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...