oj.uz

Submission #940533

# Submission time Handle Problem Language Result Execution time Memory
940533 2024-03-07T10:20:17 Z boris_mihov Reconstruction Project (JOI22_reconstruction) C++17
7 / 100
 1028 ms 71660 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];
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[MAXN];
llong addToTimes[MAXN];

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.0 / 3.0

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

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8660 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct
11 Correct 2 ms 8540 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 1 ms 8540 KB Output is correct
14 Correct 1 ms 8540 KB Output is correct
15 Correct 2 ms 8708 KB Output is correct
16 Correct 1 ms 8540 KB Output is correct
17 Correct 1 ms 8540 KB Output is correct
18 Correct 1 ms 8660 KB Output is correct
19 Correct 2 ms 8540 KB Output is correct
20 Correct 816 ms 11068 KB Output is correct
21 Correct 785 ms 11092 KB Output is correct
22 Correct 777 ms 11268 KB Output is correct
23 Correct 846 ms 11040 KB Output is correct
24 Correct 987 ms 11040 KB Output is correct
25 Correct 802 ms 10912 KB Output is correct
26 Correct 849 ms 11036 KB Output is correct
27 Correct 845 ms 11036 KB Output is correct
28 Correct 858 ms 11036 KB Output is correct
29 Correct 811 ms 11276 KB Output is correct
30 Correct 816 ms 11036 KB Output is correct
31 Correct 811 ms 11164 KB Output is correct
32 Correct 828 ms 11040 KB Output is correct
33 Correct 838 ms 11036 KB Output is correct
34 Correct 841 ms 11296 KB Output is correct
35 Correct 835 ms 11036 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8668 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Runtime error 1028 ms 71660 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8660 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct
11 Correct 2 ms 8540 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 1 ms 8540 KB Output is correct
14 Correct 1 ms 8540 KB Output is correct
15 Correct 2 ms 8708 KB Output is correct
16 Correct 1 ms 8540 KB Output is correct
17 Correct 1 ms 8540 KB Output is correct
18 Correct 1 ms 8660 KB Output is correct
19 Correct 1 ms 8536 KB Output is correct
20 Runtime error 186 ms 68296 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8660 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct
11 Correct 2 ms 8540 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 1 ms 8540 KB Output is correct
14 Correct 1 ms 8540 KB Output is correct
15 Correct 2 ms 8708 KB Output is correct
16 Correct 1 ms 8540 KB Output is correct
17 Correct 1 ms 8540 KB Output is correct
18 Correct 1 ms 8660 KB Output is correct
19 Correct 2 ms 8540 KB Output is correct
20 Correct 816 ms 11068 KB Output is correct
21 Correct 785 ms 11092 KB Output is correct
22 Correct 777 ms 11268 KB Output is correct
23 Correct 846 ms 11040 KB Output is correct
24 Correct 987 ms 11040 KB Output is correct
25 Correct 802 ms 10912 KB Output is correct
26 Correct 849 ms 11036 KB Output is correct
27 Correct 845 ms 11036 KB Output is correct
28 Correct 858 ms 11036 KB Output is correct
29 Correct 811 ms 11276 KB Output is correct
30 Correct 816 ms 11036 KB Output is correct
31 Correct 811 ms 11164 KB Output is correct
32 Correct 828 ms 11040 KB Output is correct
33 Correct 838 ms 11036 KB Output is correct
34 Correct 841 ms 11296 KB Output is correct
35 Correct 835 ms 11036 KB Output is correct
36 Incorrect 827 ms 11704 KB Output isn't correct
37 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8660 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct
11 Correct 2 ms 8540 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 1 ms 8540 KB Output is correct
14 Correct 1 ms 8540 KB Output is correct
15 Correct 2 ms 8708 KB Output is correct
16 Correct 1 ms 8540 KB Output is correct
17 Correct 1 ms 8540 KB Output is correct
18 Correct 1 ms 8660 KB Output is correct
19 Correct 2 ms 8540 KB Output is correct
20 Correct 816 ms 11068 KB Output is correct
21 Correct 785 ms 11092 KB Output is correct
22 Correct 777 ms 11268 KB Output is correct
23 Correct 846 ms 11040 KB Output is correct
24 Correct 987 ms 11040 KB Output is correct
25 Correct 802 ms 10912 KB Output is correct
26 Correct 849 ms 11036 KB Output is correct
27 Correct 845 ms 11036 KB Output is correct
28 Correct 858 ms 11036 KB Output is correct
29 Correct 811 ms 11276 KB Output is correct
30 Correct 816 ms 11036 KB Output is correct
31 Correct 811 ms 11164 KB Output is correct
32 Correct 828 ms 11040 KB Output is correct
33 Correct 838 ms 11036 KB Output is correct
34 Correct 841 ms 11296 KB Output is correct
35 Correct 835 ms 11036 KB Output is correct
36 Correct 1 ms 8540 KB Output is correct
37 Correct 1 ms 8668 KB Output is correct
38 Correct 1 ms 8540 KB Output is correct
39 Runtime error 1028 ms 71660 KB Execution killed with signal 11
40 Halted 0 ms 0 KB -