oj.uz

Submission #940510

# Submission time Handle Problem Language Result Execution time Memory
940510 2024-03-07T10:07:58 Z boris_mihov Reconstruction Project (JOI22_reconstruction) C++17
3 / 100
 918 ms 40412 KB 
#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);
        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]] == i);
        // 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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4600 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 4444 KB Output is correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4600 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 4444 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Runtime error 848 ms 15624 KB Execution killed with signal 6
21 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Runtime error 918 ms 40412 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4600 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 4444 KB Output is correct
19 Correct 1 ms 4440 KB Output is correct
20 Runtime error 95 ms 38484 KB Execution killed with signal 6
21 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4600 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 4444 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Runtime error 848 ms 15624 KB Execution killed with signal 6
21 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4600 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 4444 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Runtime error 848 ms 15624 KB Execution killed with signal 6
21 Halted 0 ms 0 KB -