Submission #1247651

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247651		Zbyszek99	Reconstruction Project (JOI22_reconstruction)	C++17	0 / 100	3 ms	7492 KiB

reconstruction

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

pii edges[100001];
ll C[100001];
int rep_[501];
int sub[501];
int last_visit[501];
int last = 1;

void reset()
{
    last++;
}
int fint(int v)
{
    int cur_v = v;
    if(last_visit[v] != last)
    {
        rep_[v] = v;
        sub[v] = 1;
        last_visit[v] = last;
        return v;
    }
    while(rep_[cur_v] != cur_v)
    {
        if(last_visit[cur_v] != last)
        {
            rep_[cur_v] = cur_v;
            sub[cur_v] = 1;
            last_visit[cur_v] = last;
            break;
        }
        cur_v = rep_[cur_v];
    }
    int v2 = v;
    int v3 = v;
    while(rep_[v2] != cur_v)
    {
        v3 = rep_[v2];
        rep_[v2] = cur_v;
        v2 = v3;
    }
    return cur_v;
}
void onion(int a, int b)
{
    a = fint(a);
    b = fint(b);
    if(a == b) return;
    if(sub[a] > sub[b]) swap(a,b);
    rep_[a] = b;
    sub[b] += sub[a];
}

vi pref_MST[100002];
vi suf_MST[100002];
vi point_MST[100001];
ll lb[100001];
ll rb[100001];
int plb[100001];
int prb[100001];

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random_start();
    int n,m;
    cin >> n >> m;
    vector<pair<int,pii>> edge_sort;
    rep(i,m)
    {
        int a,b,c;
        cin >> a >> b >> c;
        edge_sort.pb({c,{a,b}});
    }
    sort(all(edge_sort));
    rep2(i,1,m)
    {
        C[i] = edge_sort[i-1].ff;
        edges[i] = edge_sort[i-1].ss;
    }
    rep2(i,1,m)
    {
        if(fint(edges[i].ff) != fint(edges[i].ss))
        {
            pref_MST[i] = pref_MST[i-1];
            pref_MST[i].pb(i);
            onion(edges[i].ff,edges[i].ss);
            continue;
        }
        reset();
        pref_MST[i].pb(i);
        forall(it,pref_MST[i-1])
        {
            if(fint(edges[it].ff) != fint(edges[it].ss))
            {
                onion(edges[it].ff,edges[it].ss);
                pref_MST[i].pb(it);
            }
        }
    }
    for(int i = m; i >= 1; i--)
    {
        if(fint(edges[i].ff) != fint(edges[i].ss))
        {
            suf_MST[i] = suf_MST[i+1];
            suf_MST[i].pb(i);
            onion(edges[i].ff,edges[i].ss);
            continue;
        }
        reset();
        suf_MST[i].pb(i);
        forall(it,suf_MST[i+1])
        {
            if(fint(edges[it].ff) != fint(edges[it].ss))
            {
                onion(edges[it].ff,edges[it].ss);
                suf_MST[i].pb(it);
            }
        }
    }
    rep2(i,1,m)
    {
        reset();
        int cur_p = 0;
        int cur_s = 0;
        rep(j,siz(pref_MST[i]) + siz(suf_MST[i]))
        {
            int t = 0;
            if(cur_p == siz(pref_MST[i])) t = 1;
            else if(cur_s == siz(suf_MST[i])) t = 0;
            else
            {
                if(abs(C[i] - C[pref_MST[i][cur_p]]) <= abs(C[i] - C[suf_MST[i][cur_s]])) t = 0;
                else t = 1;
            }
            if(t == 0)
            {
                if(fint(edges[pref_MST[i][cur_p]].ff) != fint(edges[pref_MST[i][cur_p]].ss))
                {
                    point_MST[i].pb(pref_MST[i][cur_p]);
                    onion(edges[pref_MST[i][cur_p]].ff,edges[pref_MST[i][cur_p]].ss);
                }
                cur_p++;
            }
            else
            {
                if(fint(edges[suf_MST[i][cur_s]].ff) != fint(edges[suf_MST[i][cur_s]].ss))
                {
                    point_MST[i].pb(suf_MST[i][cur_s]);
                    onion(edges[suf_MST[i][cur_s]].ff,edges[suf_MST[i][cur_s]].ss);
                }
                cur_s++;
            }
        }
    }
    rep2(i,1,m)
    {
        plb[i] = i;
        prb[i] = i;
    }
    rep2(i,1,m)
    {
        forall(it,point_MST[i])
        {
            plb[it] = min(plb[it],i);
            prb[it] = max(prb[it],i);
        }
    }
    rep2(i,1,m)
    {
        lb[i] = C[plb[i]];
        rb[i] = C[prb[i]];
        //left
        int l = plb[i];
        int r = prb[i];
        reset();
        rep(j,siz(suf_MST[l]))
        {
            if(suf_MST[l][j] == i) break;
            onion(edges[suf_MST[l][j]].ff,edges[suf_MST[l][j]].ss);
        }
        int last_ok = -1;
        rep(j,siz(pref_MST[l-1]))
        {
            onion(edges[pref_MST[l-1][j]].ff,edges[pref_MST[l-1][j]].ss);
            if(fint(edges[i].ff) == fint(edges[i].ss)) break;
            last_ok = j;
        }
        if(last_ok == siz(pref_MST[l-1])-1) lb[i] = -1e9;
        else
        {
            lb[i] = (C[i]+C[pref_MST[l-1][last_ok+1]]+2)/2;
        }
        reset();
        rep(j,siz(pref_MST[r]))
        {
            if(pref_MST[r][j] == i) break;
            onion(edges[pref_MST[r][j]].ff,edges[pref_MST[r][j]].ss);
        }
        last_ok = -1;
        rep(j,siz(suf_MST[r+1]))
        {
            onion(edges[suf_MST[r+1][j]].ff,edges[suf_MST[r+1][j]].ss);
            if(fint(edges[i].ff) == fint(edges[i].ss)) break;
            last_ok = j;
        }
        if(last_ok == siz(suf_MST[r+1])-1) rb[i] = 1e9+5;
        else
        {
            rb[i] = (C[i]+C[suf_MST[r+1][last_ok+1]])/2;
        }
    }
    int q;
    cin >> q;
    vector<pll> events;
    rep2(i,1,m)
    {
        events.pb({lb[i],i});
        events.pb({C[i],-i});
        events.pb({rb[i]+1,i});
    }
    sort(all(events));
    int cur_event = 0;
    ll left_sum = 0;
    ll right_sum = 0;
    ll left_cnt = 0;
    ll right_cnt = 0;
    rep(qq,q)
    {
        ll x;
        cin >> x;
        while(cur_event < siz(events) && events[cur_event].ff <= x)
        {
            pll e = events[cur_event];
            cur_event++;
            if(e.ss > 0)
            {
                if(e.ff == lb[e.ss])
                {
                    left_sum += -C[e.ss];
                    left_cnt++;
                }
                else
                {
                    right_sum += -C[e.ss];
                    right_cnt--;
                }
            }
            else
            {
                left_sum += C[-e.ss];
                right_sum += C[-e.ss];
                left_cnt--;
                right_cnt++;
            }
        }
        cout << -(x*left_cnt + left_sum - x*right_cnt + right_sum) << "\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