Submission #1280024

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280024		tvgk	Reconstruction Project (JOI22_reconstruction)	C++20	100 / 100	1341 ms	20320 KiB

reconstruction

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<int, int>
const long mxN = 1e5 + 7, inf = 1e9 + 7;

struct edge
{
    int u, v, cost;
};

int n, m, h[mxN], cnt[mxN * 4], q, dsu[mxN], l[mxN], r[mxN];
ii par[mxN];
vector<ii> w[mxN], query;
ll tree[mxN * 4];
set<int> s;
edge a[mxN];

bool cmp(edge u, edge v)
{
    return u.cost < v.cost;
}

int Erase(int u, int v)
{
    int res = 0;
    while (u != v)
    {
        if (h[u] < h[v])
            swap(u, v);

        if (a[par[u].se].cost > a[res].cost)
            res = par[u].se;
        u = par[u].fi;
    }
    return res;
}

int Find(int j)
{
    if (dsu[j] == j)
        return j;
    else
        return dsu[j] = Find(dsu[j]);
}

void Union(int u, int v, int id)
{
    u = Find(u);
    v = Find(v);

    if (u != v)
    {
        dsu[v] = u;
        return;
    }

    int tmp = Erase(a[id].u, a[id].v);
    s.erase(tmp);
    r[id] = (a[id].cost + a[tmp].cost) / 2;
    l[tmp] = r[id] + 1;
}

void DFS(int j)
{
    for (ii i : w[j])
    {
        if (h[i.fi])
            continue;

        h[i.fi] = h[j] + 1;
        par[i.fi] = {j, i.se};
        DFS(i.fi);
    }
}

void Build()
{
    for (int i = 1; i <= n; i++)
    {
        w[i].clear();
        h[i] = 0;
    }

    for (int i : s)
    {
        w[a[i].u].push_back({a[i].v, i});
        w[a[i].v].push_back({a[i].u, i});
    }

    for (int i = 1; i <= n; i++)
    {
        if (h[i])
            continue;
        h[i] = 1;
        DFS(i);
    }
}

void Upd(int vt, bool tt, int j = 1, int l = 1, int r = m)
{
    if (l > vt || vt > r)
        return;

    if (l == r)
    {
        cnt[j] = tt;
        tree[j] = a[l].cost * tt;
        return;
    }

    int mid = (l + r) / 2;
    Upd(vt, tt, j * 2, l, mid);
    Upd(vt, tt, j * 2 + 1, mid + 1, r);
    tree[j] = tree[j * 2] + tree[j * 2 + 1];
    cnt[j] = cnt[j * 2] + cnt[j * 2 + 1];
}

ll Get(ll val, int j = 1, int l = 1, int r = m)
{
    if (a[r].cost <= val)
        return val * cnt[j] - tree[j];
    if (val <= a[l].cost)
        return tree[j] - val * cnt[j];

    int mid = (l + r) / 2;
    return Get(val, j * 2, l, mid) + Get(val, j * 2 + 1, mid + 1, r);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        dsu[i] = i;
    for (int i = 1; i <= m; i++)
        cin >> a[i].u >> a[i].v >> a[i].cost;
    sort(a + 1, a + m + 1, cmp);

    for (int i = m; i >= 1; i--)
    {
        l[i] = 0;
        r[i] = inf;

        Union(a[i].u, a[i].v, i);
        s.insert(i);
        Build();
    }

    for (int i = 1; i <= m; i++)
    {
        //cout << a[i].u << " " << a[i].v << " " << l[i] << " " << r[i] << '\n';

        if (l[i] > r[i])
            continue;

        query.push_back({l[i], i});
        query.push_back({r[i] + 1, -i});
    }
    sort(query.begin(), query.end());

    int q;
    cin >> q;
    int ctr = 0;
    for (int i = 1; i <= q; i++)
    {
        int tmp;
        cin >> tmp;
        while (ctr < query.size() && query[ctr].fi <= tmp)
        {
            Upd(abs(query[ctr].se), query[ctr].se > 0);
            ctr++;
        }
        cout << Get(tmp) << '\n';
    }
}

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