Submission #674063

#	Time	Username	Problem	Language	Result	Execution time	Memory
674063		doowey	Reconstruction Project (JOI22_reconstruction)	C++14	100 / 100	2482 ms	37416 KiB

reconstruction

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = 510;

struct segm{
    ll pos;
    ll coeff;
    ll add;
    bool operator< (const segm &pq){
        return pos < pq.pos;
    }
};

struct edge{
    int ui;
    int vi;
    ll weight;
    bool operator< (const edge &E) {
        return weight < E.weight;
    }
};

int par[N];

int fin(int u){
    if(par[u] == u) return u;
    return par[u]=fin(par[u]);
}

bool unite(int u, int v){
    u=fin(u);
    v=fin(v);
    if(u==v) return false;
    par[u]=v;
    return true;
}

int main(){
    fastIO;
    //freopen("in.txt", "r", stdin);
    int n, m;
    cin >> n >> m;
    vector<edge> E;
    int u, v;
    ll w;
    for(int i = 0 ; i < m ; i ++ ){
        cin >> u >> v >> w;
        w *= 2;
        E.push_back({u, v, w});
    }
    sort(E.begin(), E.end());
    int li;
    int ri;
    vector<segm> sweep;
    for(int ii = 0 ; ii < m; ii ++ ){
        for(int i = 1; i <= n; i ++ ) par[i] = i;
        li = ii - 1;
        while(li >= 0){
            unite(E[li].ui, E[li].vi);
            if(fin(E[ii].ui) == fin(E[ii].vi)){
                break;
            }
            li -- ;
        }
        for(int i = 1; i <= n; i ++ ) par[i] = i;
        ri = ii + 1;
        while(ri < E.size()){
            unite(E[ri].ui, E[ri].vi);
            if(fin(E[ii].ui) == fin(E[ii].vi)){
                break;
            }
            ri ++ ;
        }
        if(li < 0){
            sweep.push_back({0, -1, +E[ii].weight});
            sweep.push_back({E[ii].weight, +1, -E[ii].weight});
        }
        else{
            sweep.push_back({(E[ii].weight + E[li].weight) / 2ll, -1, +E[ii].weight});
            sweep.push_back({E[ii].weight, +1, -E[ii].weight});
        }
        if(ri == E.size()){
            sweep.push_back({E[ii].weight, +1, -E[ii].weight});
        }
        else{
            sweep.push_back({E[ii].weight, +1, -E[ii].weight});
            sweep.push_back({(E[ii].weight + E[ri].weight) / 2ll, -1, +E[ii].weight});
        }
    }
    sort(sweep.begin(), sweep.end());
    int id = 0;
    ll coeff = 0ll;
    ll add = 0;
    int q;
    cin >> q;
    ll xi;
    for(int iq = 1; iq <= q; iq ++ ){
        cin >> xi;
        xi *= 2ll;
        while(id < sweep.size() && sweep[id].pos <= xi){
            coeff += sweep[id].coeff;
            add += sweep[id].add;
            id ++ ;
        }
        cout << (xi * 1ll * coeff + add) / 2ll << "\n";
    }
    return 0;
}

Compilation message (stderr)

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:77:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         while(ri < E.size()){
      |               ~~~^~~~~~~~~~
reconstruction.cpp:92:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         if(ri == E.size()){
      |            ~~~^~~~~~~~~~~
reconstruction.cpp:110:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<segm>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |         while(id < sweep.size() && sweep[id].pos <= xi){
      |               ~~~^~~~~~~~~~~~~~

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