제출 #678877

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
678877		elkernos	Reconstruction Project (JOI22_reconstruction)	C++17	100 / 100	2054 ms	29748 KiB

reconstruction

#include <bits/stdc++.h>
 
using namespace std;

struct E {
  int a, b, w;
  bool operator<(const E &he) const { return w < he.w; }
};
 struct UF {
   vector<int> par;
   UF(int sz) : par(sz, -1) {}
   int root(int i) { return par[i] < 0 ? i : par[i] = root(par[i]); }
   bool join(int a, int b)
   {
     a = root(a), b = root(b);
     if (a == b) return false;
     if (par[a] > par[b]) swap(a, b);
     par[a] += par[b];
     par[b] = a;
     return true;
   }
   bool same(int a, int b) { return root(a) == root(b); }
 };

int32_t main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    vector<E> edges(m);
    for (auto &[a, b, w] : edges) {
        cin >> a >> b >> w;
    }
    sort(edges.begin(), edges.end());
    vector<pair<int, pair<int, int>>> dod;
    for (int i = 0; i < m; i++) {
        int l_when, r_when;
        {
            int l = i;
            UF uf(n + 1);
            for (int j = i - 1; j >= 0; j--) {
                uf.join(edges[j].a, edges[j].b);
                if (uf.same(edges[i].a, edges[i].b)) {
                    l = j;
                    break;
                }
            }
            l_when = (l == i ? -1 : edges[i].w - (edges[i].w - edges[l].w) / 2);
        }
        {
            int r = i;
            UF uf(n + 1);
            for (int j = i + 1; j < m; j++) {
                uf.join(edges[j].a, edges[j].b);
                if (uf.same(edges[i].a, edges[i].b)) {
                    r = j;
                    break;
                }
            }
            r_when = (r == i ? 2e9 : edges[i].w + (edges[r].w - edges[i].w + 1) / 2);
        }
        //(0 -> edges[i].c - x)
        //(edges[i].c - x -> x - edges[i].c)
        //(x - edges[i].c -> 0)
        dod.push_back({l_when, {-1, +edges[i].w}});
        dod.push_back({edges[i].w, {+2, -2 * edges[i].w}});
        dod.push_back({r_when, {-1, +edges[i].w}});
    }
    sort(dod.begin(), dod.end());
    int q;
    cin >> q;
    int p = 0;
    int64_t b = 0;
    int a = 0;
    while (q--) {
        int x;
        cin >> x;
        while (p < (int)dod.size() && dod[p].first <= x) {
            a += dod[p].second.first;
            b += dod[p].second.second;
            p++;
        }
        cout << (int64_t)a * x + b << '\n';
    }
}

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