Submission #1127522

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127522		lam	Reconstruction Project (JOI22_reconstruction)	C++20	14 / 100	5095 ms	26328 KiB

reconstruction

#include<bits/stdc++.h>
#define ll long long
#define mod (ll)(1e9+7)
#define ntr "\n"
#define taskname "RAILROAD"
#define frep freopen(taskname".inp","r",stdin); freopen("RAILROAD.out","w",stdout);
using namespace std;
vector<ll> adj[501][501];
vector<array<ll,3>> edges;
ll p[501][501];
ll par[501],sz[501];
inline ll find_par(ll u){
    return (u==par[u]?u:par[u]=find_par(par[u]));
}
inline bool uni(ll u,ll v){
    u=find_par(u);
    v=find_par(v);
    if(u==v) return 0;
    if(sz[u]<sz[v]) swap(u,v);
    par[v]=u;
    sz[u]+=sz[v];
    //cout<<"connect "<<u<<' '<<v<<ntr;
    return 1;
}
ll n,m,q;
void sub3(){
    for(int i=1;i<n;i++){
        sort(adj[i][i+1].begin(),adj[i][i+1].end());
    }
    while(q--){
        ll x;
        cin>>x;
        ll ans=0;
        for(int i=2;i<=n;i++){
            if(adj[i-1][i].size()==0){
                ans=-1;
                break;
            }
            while(p[i-1][i]<adj[i-1][i].size()){
                if(adj[i-1][i][p[i-1][i]]<=x) p[i-1][i]++;
                else break;
            }
            if(p[i-1][i]==0) ans+=adj[i-1][i][p[i-1][i]]-x;
            else if(p[i-1][i]==adj[i-1][i].size()) ans+=x-adj[i-1][i].back();
            else ans+=min(adj[i-1][i][p[i-1][i]]-x,x-adj[i-1][i][p[i-1][i]-1]);
        }
        cout<<ans<<ntr;
    }
}
void sub5(){
    ll pos=0;
    sort(edges.begin(),edges.end());
    while(q--){
        ll x;
        cin>>x;
        for(int i=1;i<=n;i++) par[i]=i,sz[i]=1;
        ll ans=0;
        while(pos<m){
            if(edges[pos][0]<=x) pos++;
            else break;
        }
        ll p1=pos-1,p2=pos;
        while(p1>=0||p2<m){
            if(sz[find_par(1)]==n) break;
//            cout<<ans<<ntr;
            if(p1<0){
//                cout<<edges[p2][0]<<' '<<edges[p2][1]<<' '<<edges[p2][2]<<ntr;
                if(uni(edges[p2][1],edges[p2][2])) ans+=edges[p2][0]-x;
                p2++;
            }
            else if(p2>=m){
//                cout<<edges[p1][0]<<' '<<edges[p1][1]<<' '<<edges[p1][2]<<ntr;
                if(uni(edges[p1][1],edges[p1][2])) ans+=x-edges[p1][0];
                p1--;
            }
            else{
                if(edges[p2][0]-x<x-edges[p1][0]){
//                    cout<<edges[p2][0]<<' '<<edges[p2][1]<<' '<<edges[p2][2]<<ntr;
                    if(uni(edges[p2][1],edges[p2][2])) ans+=edges[p2][0]-x;
                    p2++;
                }
                else{
//                    cout<<edges[p1][0]<<' '<<edges[p1][1]<<' '<<edges[p1][2]<<ntr;
                    if(uni(edges[p1][1],edges[p1][2])) ans+=x-edges[p1][0];
                    p1--;
                }
            }
        }
        if(sz[find_par(1)]==n) cout<<ans<<ntr;
        else cout<<-1<<ntr;
    }
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>m;
    ll mx=0;
    for(int i=1;i<=m;i++){
        ll a,b,c;
        cin>>a>>b>>c;
        mx=max(mx,abs(a-b));
        adj[a][b].push_back(c);
        adj[b][a].push_back(c);
        edges.push_back({c,a,b});
    }
    cin>>q;
    if(mx<=1)
        sub3();
    else
        sub5();
}

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