Submission #1089714

#TimeUsernameProblemLanguageResultExecution timeMemory
1089714hahahahaReconstruction Project (JOI22_reconstruction)C++17
100 / 100
546 ms29436 KiB
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "debug.h" #else #define debug(...) 42 #endif const int N = 505, M = 1e5 + 5, inf = 1e9; int n, m, q; int mn[N]; vector<array<int, 2>> g[N]; array<int, 3> edges[M]; void add(int u, int v, int w) { g[u].push_back({v, w}); g[v].push_back({u, w}); } void ers(int u, int v, int w) { g[u].erase(find(g[u].begin(), g[u].end(), array<int, 2>{v, w})); g[v].erase(find(g[v].begin(), g[v].end(), array<int, 2>{u, w})); } void dfs(int u, int p) { for (auto [v, w] : g[u]) { if (v != p) { mn[v] = min(mn[u], w); dfs(v, u); } } } int get(int u, int v) { fill(mn + 1, mn + n + 1, m + 1); dfs(u, u); return mn[v]; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m; for (int i = 1; i <= m; ++i) { cin >> edges[i][1] >> edges[i][2] >> edges[i][0]; } sort(edges + 1, edges + m + 1); vector<array<int, 3>> events; for (int i = 1; i <= m; ++i) { auto [c, u, v] = edges[i]; int lt = get(u, v); if (lt != m + 1) { auto [w, x, y] = edges[lt]; int md = (w + 1 + c) / 2; events.push_back({md, w + c, -2}); ers(x, y, lt); } else { events.push_back({0, c, -1}); } events.push_back({c, -2 * c, 2}); add(u, v, i); } sort(events.begin(), events.end()); cin >> q; int j = 0, B = 0; long long A = 0; while (q--) { int X; cin >> X; while (j < events.size() && events[j][0] <= X) { A += events[j][1]; B += events[j][2]; ++j; } cout << (long long) B * X + A << "\n"; } return 0; }

Compilation message (stderr)

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:72:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     while (j < events.size() && events[j][0] <= 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...