Submission #781690

#	Time	Username	Problem	Language	Result	Execution time	Memory
781690		PoonYaPat	Reconstruction Project (JOI22_reconstruction)	C++14	100 / 100	1273 ms	35060 KiB

reconstruction

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

struct Edge {
    ll w,a,b;
    bool operator < (const Edge &o) const {return w<o.w;}
};

int n,m,bef[100005],aft[100005],p[505],r[505];
Edge edge[100005];
vector<Edge> v;

int find(int x) {
    while (x!=p[x]) x=p[x];
    return x;
}

void unite(int a, int b) {
    a=find(a); b=find(b);
    if (a!=b) {
        if (r[a]>r[b]) swap(a,b);
        p[a]=b;
        if (r[a]==r[b]) ++r[b];
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    for (int i=1; i<=m; ++i) cin>>edge[i].a>>edge[i].b>>edge[i].w;
    sort(edge+1,edge+m+1);

    for (int i=1; i<=m; ++i) {
        bef[i]=i-1;
        for (int j=1; j<=n; ++j) r[j]=1, p[j]=j;
        while (bef[i]) {
            unite(edge[bef[i]].a,edge[bef[i]].b);
            if (find(edge[i].a)==find(edge[i].b)) break;
            --bef[i];
        }
    }

    for (int i=1; i<=m; ++i) aft[i]=m+1;
    for (int i=1; i<=m; ++i) aft[bef[i]]=i;

    for (int i=1; i<=m; ++i) {
        if (bef[i]) v.push_back({(edge[i].w+edge[bef[i]].w)/2+1,-1ll,edge[i].w});
        else v.push_back({0,-1ll,edge[i].w});

        v.push_back({edge[i].w,2ll,-2*edge[i].w});

        if (aft[i]!=m+1) v.push_back({(edge[i].w+edge[aft[i]].w)/2+1,-1ll,edge[i].w});
    }
    sort(v.begin(),v.end());

    int q; cin>>q;
    int idx=0;
    ll cnt1=0,cnt2=0;
    while (q--) {
        ll x; cin>>x;
        while (idx<v.size() && v[idx].w<=x) {
            cnt1+=v[idx].a;
            cnt2+=v[idx].b;
            ++idx;
        }
        cout<<cnt1*x+cnt2<<"\n";
    }
}

Compilation message (stderr)

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:62:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         while (idx<v.size() && v[idx].w<=x) {
      |                ~~~^~~~~~~~~

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