Submission #951347

#	Time	Username	Problem	Language	Result	Execution time	Memory
951347		Nhoksocqt1	Road Closures (APIO21_roads)	C++17	12 / 100	39 ms	8916 KiB

roads

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

#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 100005;

class DisjointSet {
    private:
        vector<int> lab;

    public:
        DisjointSet(int _n = 0) {
            lab.assign(_n + 7, -1);
        }

        int find(int u) {
            return (lab[u] < 0) ? u : (lab[u] = find(lab[u]));
        }

        bool join(int u, int v) {
            u = find(u), v = find(v);
            if(u == v)
                return (false);

            if(lab[u] > lab[v])
                swap(u, v);

            lab[u] += lab[v];
            lab[v] = u;
            return (true);
        }
} dsu;

struct Edge {
    int u, v, w;
} edge[MAXN];

ll dp[MAXN][2];
int deg[MAXN], numNode;

vector<ll> sub1(void) {
    sort(edge, edge + numNode - 1, [](const Edge &a, const Edge &b) {
        return (a.w > b.w);
    });

    vector<ll> ans;
    ll sumCost(0);
    for (int i = 0; i < numNode - 1; ++i)
        sumCost += edge[i].w;

    for (int i = 0; i < numNode; ++i) {
        ans.push_back(sumCost);
        sumCost -= edge[i].w;
    }

    return ans;
}

vector<ll> sub2(void) {
    vector<ll> ans;
    ll sumCost(0);

    dp[0][0] = dp[0][1] = 0;
    for (int i = 0; i < numNode - 1; ++i) {
        sumCost += edge[i].w;
        dp[i + 1][0] = max(dp[i][1], dp[i][0]);
        dp[i + 1][1] = dp[i][0] + edge[i].w;
    }

    ans.push_back(sumCost);
    ans.push_back(sumCost - max(dp[numNode - 1][0], dp[numNode - 1][1]));

    for (int i = 2; i < numNode; ++i)
        ans.push_back(0);

    return ans;
}

vector<ll> minimum_closure_costs(int _N, vector<int> _U, vector<int> _V, vector<int> _W) {
    numNode = _N;

    bool check_sub1(1), check_sub2(1);
    for (int i = 0; i + 1 < numNode; ++i) {
        edge[i] = {_U[i], _V[i], _W[i]};
        if(edge[i].u > edge[i].v)
            swap(edge[i].u, edge[i].v);

        check_sub1 &= (edge[i].u == 0);
        check_sub2 &= (edge[i].u == i && edge[i].v == i + 1);
    }

    if(check_sub1)
        return sub1();

    if(check_sub2)
        return sub2();

    return {-1};
}

#ifdef Nhoksocqt1

int main(void) {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    #define TASK "roads"
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }

    vector<int> u, v, w;
    int n;
    cin >> n;

    u.resize(n - 1), v.resize(n - 1), w.resize(n - 1);
    for (int i = 0; i + 1 < n; ++i) {
        cin >> u[i] >> v[i] >> w[i];
    }

    vector<ll> ans = minimum_closure_costs(n, u, v, w);
    cout << "ANSWER: ";
    for (int it = 0; it < sz(ans); ++it)
        cout << ans[it] << ' '; cout << '\n';

    return 0;
}

#endif // Nhoksocqt1

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 0 / 14
• Subtask 4: 0 / 10
• Subtask 5: 0 / 17
• Subtask 6: 0 / 25
• Subtask 7: 0 / 22