Submission #940518

#	Time	Username	Problem	Language	Result	Execution time	Memory
940518		boris_mihov	Reconstruction Project (JOI22_reconstruction)	C++17	3 / 100	900 ms	40404 KiB

reconstruction

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

#define int long long
typedef long long llong;
const int MAXN = 500 + 10;
const int MAXM = 100000 + 10;
const int MAXQ = 1000000 + 10;

int n, m, q;
struct Edge
{
    int u, v, cost;
    friend bool operator < (const Edge &a, const Edge &b)
    {
        return a.cost < b.cost;
    }
};

Edge e[MAXM];
llong answer[MAXQ];
std::vector <std::pair <int,int>> g[MAXN];
std::pair <int,int> queries[MAXQ];
int leftMAX[MAXN];
int rightMIN[MAXN];
int startT[MAXN];
int endT[MAXN];
int edge[MAXN];
int par[MAXN];

void addEdge(int u, int v, int idx)
{
    g[u].push_back({v, idx});
    g[v].push_back({u, idx});
}

void removeEdge(int u, int v)
{
    for (auto &x : g[u])
    {   
        if (x.first == v)
        {
            std::swap(x, g[u].back());
            g[u].pop_back();
            break;
        }
    }

    for (auto &x : g[v])
    {   
        if (x.first == u)
        {
            std::swap(x, g[v].back());
            g[v].pop_back();
            break;
        }
    }
}

void rebuildDFS(int node)
{
    for (const auto &[u, idx] : g[node])
    {
        if (u == par[node])
        {
            continue;
        }

        par[u] = node;
        edge[u] = idx;
        rebuildDFS(u);
    }
}

bool vis[MAXN];
int findLCA(int u, int v)
{
    std::fill(vis + 1, vis + 1 + n, false);
    int node = v;
    while (node != 0)
    {
        vis[node] = true;
        node = par[node];
    }

    node = u;
    while (!vis[node])
    {
        node = par[node];
    }

    return node;
}

int findChainMAX(int u, int v)
{
    if (u == v) return 0;
    int res = findChainMAX(par[u], v);
    if (res == 0 || edge[u] > edge[res]) return u;
    else return res;
}

int findChainMIN(int u, int v)
{
    if (u == v) return 0;
    int res = findChainMIN(par[u], v);
    if (res == 0 || edge[u] < edge[res]) return u;
    else return res;
}

int findMAX(int u, int v)
{
    int lca = findLCA(u, v);
    int resU = findChainMAX(u, lca);
    int resV = findChainMAX(v, lca);
    if (resU == 0 || (resV != 0 && edge[resV] > edge[resU])) return resV;
    else return resU;
}

int findMIN(int u, int v)
{
    int lca = findLCA(u, v);
    int resU = findChainMIN(u, lca);
    int resV = findChainMIN(v, lca);
    if (resU == 0 || (resV != 0 && edge[resV] < edge[resU])) return resV;
    else return resU;
}

void solve()
{
    std::sort(e + 1, e + 1 + m);
    for (int i = 1 ; i <= n ; ++i)
    {
        g[i].clear();
    }

    for (int i = 1 ; i < n ; ++i)
    {
        g[i].push_back({i + 1, 0});
        g[i + 1].push_back({i, 0});
    }

    par[1] = 0;
    edge[1] = m + 1;
    rebuildDFS(1);

    for (int i = 1 ; i <= m ; ++i)
    {
        int res = findMIN(e[i].u, e[i].v);
        assert(res > 1 && res <= n);
        leftMAX[i] = edge[res];
        removeEdge(res, par[res]);
        addEdge(e[i].u, e[i].v, i);
        
        par[1] = 0;
        edge[1] = m + 1;
        rebuildDFS(1);
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        g[i].clear();
    }

    for (int i = 1 ; i < n ; ++i)
    {
        g[i].push_back({i + 1, m + 1});
        g[i + 1].push_back({i, m + 1});
    }

    par[1] = 0;
    edge[1] = 0;
    rebuildDFS(1);

    for (int i = m ; i >= 1 ; --i)
    {
        int res = findMAX(e[i].u, e[i].v);
        assert(res > 1 && res <= n);
        rightMIN[i] = edge[res];
        removeEdge(res, par[res]);
        addEdge(e[i].u, e[i].v, i);
        
        par[1] = 0;
        edge[1] = 0;
        rebuildDFS(1);
    }

    // for (int i = 1 ; i <= m ; ++i)
    // {
    //     rightMIN[i] = m + 1;
    // }

    for (int i = 1 ; i <= m ; ++i)
    {
        if (leftMAX[i] != 0) assert(rightMIN[leftMAX[i]] != m + 1);
        // rightMIN[leftMAX[i]] = i;
    }

    for (int i = 1 ; i <= m ; ++i)
    {
        if (leftMAX[i] == 0)
        {
            startT[i] = 1;
        } else
        {
            startT[i] = (e[i].cost + e[leftMAX[i]].cost + 2) / 2;
        }

        if (rightMIN[i] == m + 1)
        {
            endT[i] = 1e9;
        } else
        {
            endT[i] = (e[rightMIN[i]].cost + e[i].cost) / 2;
        }
    }

    for (int i = 1 ; i <= q ; ++i)
    {
        llong res = 0;
        int cntIn = 0;

        for (int j = 1 ; j <= m ; ++j)
        {
            if (startT[j] <= queries[i].first && queries[i].first <= endT[j])
            {
                cntIn++;
                res += abs(queries[i].first - e[j].cost);
            }
        }

        // assert(cntIn == n - 1);
        answer[i] = res;
    }
}

void print()
{
    for (int i = 1 ; i <= q ; ++i)
    {
        std::cout << answer[i] << '\n';
    }
}

void input()
{
    std::cin >> n >> m;
    for (int i = 1 ; i <= m ; ++i)
    {
        std::cin >> e[i].u >> e[i].v >> e[i].cost;
    }

    std::cin >> q;
    for (int i = 1 ; i <= q ; ++i)
    {
        std::cin >> queries[i].first;
        queries[i].second = i;
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

signed main()
{
    fastIOI();
    input();
    solve();
    print();

    return 0;
}

/*
5 10
1 2 8
1 3 13
1 4 5
1 5 11
1 5 3
2 3 7
2 4 15
3 4 6
3 5 6
4 5 2
1
3
6
8
10
13
17
*/

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