Submission #1127530

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127530		lam	Reconstruction Project (JOI22_reconstruction)	C++20	7 / 100	5093 ms	2788 KiB

reconstruction

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

#define task "railroad"
#define etr "\n"
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define range(x, l, r) x+l, x+1+r

void freop()
{
    freopen(task".inp", "r", stdin);
    freopen(task".out", "w", stdout);
}

template<class U, class V> ostream& operator << (ostream& out, vector<U, V> v)
{
    out << "(" << v.fi << ", " << v.se << ")";
    return out;
}

template<class T> ostream& operator << (ostream& out, vector<T> v)
{
    out << "{";
    for (int i=0; i<v.size(); i++)
    {
        out << v[i];
        if (i != v.size() - 1) out << ", ";
    }

    out << "}";
    return out;
}

const int N = 500, M = 1e5;

int n, m, q;
array<int, 3> a[M+5];

namespace Sub2
{
    struct DSU
    {
        vector<int> par;

        DSU() : par(n+5, -1) {}

        int root(int u)
        {
            return par[u] < 0 ? u : par[u] = root(par[u]);
        }

        bool connect(int u, int v)
        {
            u = root(u), v = root(v);

            if (u == v) return false;

            if (-par[u] < -par[v]) swap(u, v);
            par[u] += par[v];
            par[v] = u;

            return true;
        }

    };

    array<int, 3> tmp[M+5];

    ll calc(int x)
    {
        DSU dsu;

        for (int i=1; i<=m; i++)
        {
            tmp[i] = a[i];
            tmp[i][2] = abs(x - a[i][2]);
        }

        sort(range(tmp, 1, m), [](array<int, 3> x, array<int, 3> y){return x[2] < y[2];});

        ll res = 0;
        for (int i=1; i<=m; i++)
        {
            if (dsu.connect(tmp[i][0], tmp[i][1]))
            {
                res += tmp[i][2];
            }
        }

        return res;
    }

    void solve()
    {
        for (int i=1; i<=q; i++)
        {
            int x;
            cin >> x;

            cout << calc(x) << etr;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    // freop();

    cin >> n >> m;
    for (int i=1; i<=m; i++)
    {
        for (int j=0; j<3; j++) cin >> a[i][j];
    }

    cin >> q;

    Sub2::solve();
}

Compilation message (stderr)

reconstruction.cpp: In function 'void freop()':
reconstruction.cpp:18:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     freopen(task".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:19:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     freopen(task".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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