Submission #1281616

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281616		duckindog	Reconstruction Project (JOI22_reconstruction)	C++20	100 / 100	643 ms	42404 KiB

reconstruction

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 100'000 + 10;
int n, m, q;
struct Edge { 
    int u, v, w;
    friend istream& operator >> (istream& is, Edge& rhs) { 
        return is >> rhs.u >> rhs.v >> rhs.w;
    }
} edge[N];

namespace DSU { 
    int id[510];
    static inline void init() { memset(id, -1, sizeof id); }
    static int root(int u) { return id[u] < 0 ? u : id[u] = root(id[u]); }
    static void join(int u, int v) { 
        u = root(u); v = root(v);
        if (id[u] > id[v]) swap(u, v);
        if (u == v) return;
        id[u] += id[v];
        id[v] = u;
    }
    static inline bool isConnect(int u, int v) { return root(u) == root(v); }
}

long long L[N], R[N];

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> m;
    for (int i = 1; i <= m; ++i) cin >> edge[i];
    
    sort(edge + 1, edge + m + 1, [](const auto& i, const auto& j) { 
        return i.w < j.w;
    });

    fill(R + 1, R + m + 1, 1'000'000'010);
    for (int i = 1; i <= m; ++i) { 
        DSU::init();
        for (int j = i - 1; j >= 1; --j) { 
            DSU::join(edge[j].u, edge[j].v);
            if (DSU::isConnect(edge[i].u, edge[i].v)) { 
                R[j] = L[i] = (edge[j].w + edge[i].w + 1) / 2;
                break;
            }
        }
    }

    map<int, int> lt, rt;
    for (int i = 1; i <= m; ++i) { 
        lt[L[i]] -= 1;
        lt[edge[i].w] += 2;
        lt[R[i]] -= 1;

        rt[L[i]] += edge[i].w;
        rt[edge[i].w] -= 2 * edge[i].w;
        rt[R[i]] += edge[i].w;
    }

    int cnt = 0;
    long long sum = 0;

    auto itL = lt.begin(), itR = rt.begin();
    cin >> q;
    while (q--) { 
        int x; cin >> x;

        for (; itL != lt.end() && itL->first <= x; ++itL, ++itR) { 
            cnt += itL->second;
            sum += itR->second;
        }

        cout << 1ll * x * cnt + sum << "\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