제출 #575100

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
575100		Sorting	Reconstruction Project (JOI22_reconstruction)	C++17	42 / 100	5089 ms	415800 KiB

reconstruction

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
template<class T> void check_min(T &a, const T &b){ a = (a < b) ? a : b; }
template<class T> void check_max(T &a, const T &b){ a = (a > b) ? a : b; }
#define all(x) (x).begin(), (x).end()

const int N = 500 + 3;
const int M = 1e5 + 3;
const int Q = 1e6 + 3;
const int INF = 1e9;

int n, m, q;
array<ll, 3> e[M];
ll x[Q];

struct DSU{
    int sz[N], par[N];

    void init(int n){
        for(int i = 1; i <= n; ++i)
            sz[i] = 1, par[i] = i;
    }

    int getP(int x){
        if(par[x] == x) return x;
        return par[x] = getP(par[x]);
    }

    bool unite(int a, int b){
        a = getP(a), b = getP(b);
        if(a == b) return false;
        if(sz[a] < sz[b]) swap(a, b);
        sz[a] += sz[b];
        par[b] = a;
        return true;
    }
} dsu;

vector<int> pr[M], su[M];

pair<ll, int> get_ans(const vector<int> &e1, const vector<int> &e2, ll x, int ptr){
    ll ans = 0;
    int cnt = 0;

    vector<pair<int, int>> e3;
    int ptr1 = 0, ptr2 = 0;
    while(ptr1 != e1.size() && ptr2 != e2.size()){
        int cost1 = x - e[e1[ptr1]][0];
        int cost2 = e[e2[ptr2]][0] - x;

        if(cost1 < cost2)
            e3.push_back({cost1, e1[ptr1++]});
        else
            e3.push_back({cost2, e2[ptr2++]});
    }
    while(ptr1 != e1.size()){
        int cost1 = x - e[e1[ptr1]][0];
        e3.push_back({cost1, e1[ptr1++]});
    }
    while(ptr2 != e2.size()){
        int cost2 = e[e2[ptr2]][0] - x;
        e3.push_back({cost2, e2[ptr2++]});
    }
    
    dsu.init(n);
    for(auto [cost, idx]: e3){
        if(dsu.unite(e[idx][1], e[idx][2])){
            ans += cost;
            if(idx >= ptr)
                ++cnt;
        }
    }

    return {ans, cnt};
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    for(int i = 0; i < m; ++i){
        cin >> e[i][1] >> e[i][2] >> e[i][0];
    }
    sort(e, e + m);

    pr[0] = {0};
    for(int i = 1; i < m; ++i){
        dsu.init(n);
        pr[i].push_back(i);
        for(int idx: pr[i - 1])
            if(dsu.unite(e[idx][1], e[idx][2]))
                pr[i].push_back(idx);
    }

    su[m - 1] = {m - 1};
    for(int i = m - 2; i >= 0; --i){
        dsu.init(n);
        su[i].push_back(i);
        for(int idx: su[i + 1])
            if(dsu.unite(e[idx][1], e[idx][2]))
                su[i].push_back(idx);
    }

    ll ans = 0, cnt = 0, prevx = -INF, next_change;
    auto p = get_ans({}, su[0], prevx, 0);
    ans = p.first;
    cnt = p.second;

    int ptr = 0;
    cin >> q;
    for(int i = 0; i < q; ++i){
        cin >> x[i];
        while(ptr != m && x[i] >= e[ptr][0])
            ++ptr;

        vector<int> e1;
        if(0 <= ptr - 1){
            e1 = pr[ptr - 1];
        }
        vector<int> e2;
        if(ptr <= m - 1){
            e2 = su[ptr];
        }

        auto p = get_ans(e1, e2, x[i], ptr);
        ans = p.first;
        cnt = p.second;

        cout << ans << "\n";
    }
}

컴파일 시 표준 에러 (stderr) 메시지

reconstruction.cpp: In function 'std::pair<long long int, int> get_ans(const std::vector<int>&, const std::vector<int>&, ll, int)':
reconstruction.cpp:50:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     while(ptr1 != e1.size() && ptr2 != e2.size()){
      |           ~~~~~^~~~~~~~~~~~
reconstruction.cpp:50:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     while(ptr1 != e1.size() && ptr2 != e2.size()){
      |                                ~~~~~^~~~~~~~~~~~
reconstruction.cpp:59:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     while(ptr1 != e1.size()){
      |           ~~~~~^~~~~~~~~~~~
reconstruction.cpp:63:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     while(ptr2 != e2.size()){
      |           ~~~~~^~~~~~~~~~~~
reconstruction.cpp: In function 'int main()':
reconstruction.cpp:108:17: warning: variable 'cnt' set but not used [-Wunused-but-set-variable]
  108 |     ll ans = 0, cnt = 0, prevx = -INF, next_change;
      |                 ^~~
reconstruction.cpp:108:40: warning: unused variable 'next_change' [-Wunused-variable]
  108 |     ll ans = 0, cnt = 0, prevx = -INF, next_change;
      |                                        ^~~~~~~~~~~

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