Submission #1063153

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063153		12345678	Reconstruction Project (JOI22_reconstruction)	C++17	0 / 100	196 ms	34856 KiB

reconstruction

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=5e2+5, mx=1e5+5;

ll n, m, x, q, dsu[nx], l[mx], r[mx], lz, lst, sp;
vector<pair<ll, pair<ll, ll>>> edg;
vector<pair<ll, ll>> slope;

int find(int x)
{
    if (dsu[x]==x) return x;
    return dsu[x]=find(dsu[x]);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    edg.resize(m);
    for (auto &x:edg) cin>>x.second.first>>x.second.second>>x.first;
    sort(edg.begin(), edg.end());
    for (int i=0; i<m; i++)
    {
        l[i]=-1;
        r[i]=m;
        for (int j=1; j<=n; j++) dsu[j]=j;
        for (int k=i; k>=0; k--)
        {
            if (find(edg[k].second.first)==find(edg[k].second.second)) 
            {
                l[i]=k, r[l[i]]=i;
                break;
            }
            dsu[find(edg[k].second.first)]=find(edg[k].second.second);
        }
    }
    for (int i=0; i<m; i++)
    {
        //cout<<"edge "<<edg[i].second.first<<' '<<edg[i].second.second<<' '<<edg[i].first<<' '<<l[i]<<' '<<r[i]<<'\n';
        if (l[i]==-1) lz+=edg[i].first, slope.push_back({0, -1}), slope.push_back({edg[i].first, 1});
        else
        {
            ll loc=(edg[l[i]].first+edg[i].first+1)/2;
            //lz+=edg[i].first-loc;
            slope.push_back({loc, -1});
            slope.push_back({edg[i].first, 1});
        }
        if (r[i]==m) slope.push_back({edg[i].first, 1});
        else
        {
            ll loc=(edg[i].first+edg[r[i]].first)/2;
            slope.push_back({edg[i].first, 1});
            slope.push_back({loc, -1});
        }
    }
    //cout<<"lz "<<lz<<'\n';
    sort(slope.begin(), slope.end());
    reverse(slope.begin(), slope.end());
    cin>>q;
    while (q--)
    {
        cin>>x;
        while (!slope.empty()&&slope.back().first<=x)
        {
            //cout<<"here "<<sp<<' '<<slope.back().first<<'\n';
            lz+=(slope.back().first-lst)*sp;
            sp+=slope.back().second;
            lst=slope.back().first;
            slope.pop_back();
        }
        cout<<lz+sp*(x-lst)<<'\n';
    }
}

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