Submission #940538

#	Time	Username	Problem	Language	Result	Execution time	Memory
940538		boris_mihov	Reconstruction Project (JOI22_reconstruction)	C++17	100 / 100	1042 ms	62552 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];
int queries[MAXQ];
llong answer[MAXQ];
std::vector <std::pair <int,int>> g[MAXN];
int leftMAX[MAXM];
int rightMIN[MAXM];
int startT[MAXM];
int endT[MAXM];
int edge[MAXM];
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;
}

llong addToSum[MAXQ];
llong addToTimes[MAXQ];

int firstBiggerQuery(int val)
{
    int l = 0, r = q + 1, mid;
    while (l < r - 1)
    {
        mid = (l + r) / 2;
        if (queries[mid] < val) l = mid;
        else r = mid;
    }

    return r;
}

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)
    {
        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 <= m ; ++i)
    {
        int l = firstBiggerQuery(startT[i]);
        int mid = firstBiggerQuery(e[i].cost);
        int r = firstBiggerQuery(endT[i] + 1);

        addToSum[l] += e[i].cost;
        addToSum[mid] += -2 * e[i].cost;
        addToSum[r] += e[i].cost;

        addToTimes[l] += -1;
        addToTimes[mid] += 2;
        addToTimes[r] += -1;
    }

    llong times = 0;
    llong sum = 0;

    for (int i = 1 ; i <= q ; ++i)
    {
        sum += addToSum[i];
        times += addToTimes[i];
        answer[i] = times * queries[i] + sum;
    }
}

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];
    }
}

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: 4 / 4
• Subtask 3: 7 / 7
• Subtask 4: 28 / 28
• Subtask 5: 35 / 35
• Subtask 6: 23 / 23