Submission #812728

#	Time	Username	Problem	Language	Result	Execution time	Memory
812728		thimote75	Reconstruction Project (JOI22_reconstruction)	C++14	100 / 100	2090 ms	31212 KiB

reconstruction

#include <bits/stdc++.h>
#define int long long

using namespace std;

using idata = vector<int>;
using igrid = vector<idata>;

using di = pair<int, int>;
using vd = vector<di>;

template<typename A, typename B>
string to_string (pair<A, B> p) {
    return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename T>
string to_string(T x) {
    string S = "[";
    bool first = true;
    for (const auto v: x) {
        if (!first) S += ", ";
        S += to_string(v);
        first = false;
    }
    S += "]";
    return S;
}
string to_string( string S ){
    return S;
}

void dbg_out () {
    cout << endl;
}
template<typename Head, typename... Tail>
void dbg_out (Head H, Tail... T) {
    cout << to_string(H) << " ";
    dbg_out(T...);
}

#ifdef DEBUG
#  define dbg(...) { cout << "(" << #__VA_ARGS__ << "): "; dbg_out(__VA_ARGS__); }
#else
#  define dbg(...)
#endif

struct Road {
    int a, b, cost;
    int xr;

    Road (int _a, int _b, int _cost) : a(_a), b(_b), cost(_cost) {
        xr = _a ^ _b;
    }
    inline int next (int node) {
        return xr ^ node;
    }

    bool operator< (const Road &other) {
        return cost < other.cost;
    }
};

using t_Roads = vector<Road>;
using bdata   = vector<bool>;

t_Roads road_array;

igrid road_indices;
bdata isUsing;

idata visited; int stage = 1;
bool dfs (int node, int target, pair<int, int> &ans) {
    if (node == target) return true;
    if (visited[node] == stage) return false;
    visited[node] = stage;

    for (int iR : road_indices[node]) {
        Road &road = road_array[iR];
        int next = road.next(node);

        if (dfs(next, target, ans)) {
            if (road.cost < ans.first)
                ans = { road.cost, iR };
            return true;
        }
    }

    return false;
}

struct UFD {
    idata parents;

    UFD (int size) {
        parents.resize(size);
        iota(parents.begin(), parents.end(), 0);
    }

    int boss (int x) {
        if (parents[x] != x)
            parents[x] = boss(parents[x]);
        return parents[x];
    }
    void merge (int a, int b) {
        a = boss(a); b = boss(b);
        parents[a] = b;
    }
};

signed main () {
    int N, M;
    cin >> N >> M;

    road_indices.resize(N);

    for (int i = 0; i < M; i ++) {
        int a, b, c;
        cin >> a >> b >> c;
        a --; b --;

        road_array.push_back( Road(a, b, c) );
    }

    sort(road_array.begin(), road_array.end());

    UFD ufd(N);
    isUsing.resize(M);
    int cost  = 0;
    int slope = - (N - 1);
    vd slope_modifications;
    for (int i = 0; i < M; i ++) {
        Road &road = road_array[i];

        if (ufd.boss(road.a) == ufd.boss(road.b)) continue ;
        ufd.merge(road.a, road.b);

        road_indices[road.a].push_back(i);
        road_indices[road.b].push_back(i);
        isUsing[i] = true;

        slope_modifications.push_back({ road.cost * 2, 2 });
        cost += 2 * road.cost;
    }

    visited.resize(N);
    for (int i = 0; i < M; i ++) {
        if (isUsing[i]) continue ;

        pair<int, int> answer = { 1e18, -1 };

        Road &new_road = road_array[i];
        stage ++;
        if (!dfs(new_road.a, new_road.b, answer)) continue ;

        Road &old_road = road_array[answer.second];
        slope_modifications.push_back({ new_road.cost + old_road.cost, - 2 });
        slope_modifications.push_back({ new_road.cost * 2, 2 });

        road_indices[old_road.a].erase(
            find(
                road_indices[old_road.a].begin(), 
                road_indices[old_road.a].end(), 
                answer.second
            )
        );
        road_indices[old_road.b].erase(
            find(
                road_indices[old_road.b].begin(), 
                road_indices[old_road.b].end(), 
                answer.second
            )
        );

        road_indices[new_road.a].push_back(i);
        road_indices[new_road.b].push_back(i);
    }

    sort(slope_modifications.begin(), slope_modifications.end());

    int last = 0; int modId = 0;
    int Q; cin >> Q;
    for (int q = 0; q < Q; q ++) {
        int t; cin >> t; t *= 2;
        while (modId != slope_modifications.size() && slope_modifications[modId].first < t) {
            int delta = slope_modifications[modId].first - last;
            cost += slope * delta;

            last  += delta;
            slope += slope_modifications[modId].second;
            modId ++;
        }

        int delta = t - last;
        cost += slope * delta;
        last += delta;

        cout << (cost >> 1) << "\n";
    }
}

Compilation message (stderr)

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:185:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  185 |         while (modId != slope_modifications.size() && slope_modifications[modId].first < t) {
      |                ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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