oj.uz

Submission #940538

# Submission time Handle Problem Language Result Execution time Memory
940538 2024-03-07T10:20:57 Z boris_mihov Reconstruction Project (JOI22_reconstruction) C++17
100 / 100
 1042 ms 62552 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[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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12728 KB Output is correct
5 Correct 2 ms 12632 KB Output is correct
6 Correct 2 ms 12636 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Correct 2 ms 12680 KB Output is correct
9 Correct 2 ms 12636 KB Output is correct
10 Correct 2 ms 12636 KB Output is correct
11 Correct 2 ms 12636 KB Output is correct
12 Correct 1 ms 12636 KB Output is correct
13 Correct 2 ms 12636 KB Output is correct
14 Correct 2 ms 12636 KB Output is correct
15 Correct 2 ms 12888 KB Output is correct
16 Correct 2 ms 12636 KB Output is correct
17 Correct 2 ms 12636 KB Output is correct
18 Correct 2 ms 12632 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12728 KB Output is correct
5 Correct 2 ms 12632 KB Output is correct
6 Correct 2 ms 12636 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Correct 2 ms 12680 KB Output is correct
9 Correct 2 ms 12636 KB Output is correct
10 Correct 2 ms 12636 KB Output is correct
11 Correct 2 ms 12636 KB Output is correct
12 Correct 1 ms 12636 KB Output is correct
13 Correct 2 ms 12636 KB Output is correct
14 Correct 2 ms 12636 KB Output is correct
15 Correct 2 ms 12888 KB Output is correct
16 Correct 2 ms 12636 KB Output is correct
17 Correct 2 ms 12636 KB Output is correct
18 Correct 2 ms 12632 KB Output is correct
19 Correct 2 ms 12636 KB Output is correct
20 Correct 835 ms 13336 KB Output is correct
21 Correct 809 ms 13316 KB Output is correct
22 Correct 769 ms 13344 KB Output is correct
23 Correct 771 ms 13596 KB Output is correct
24 Correct 881 ms 13564 KB Output is correct
25 Correct 801 ms 13488 KB Output is correct
26 Correct 809 ms 13340 KB Output is correct
27 Correct 950 ms 13348 KB Output is correct
28 Correct 828 ms 13344 KB Output is correct
29 Correct 900 ms 13236 KB Output is correct
30 Correct 851 ms 13344 KB Output is correct
31 Correct 833 ms 13340 KB Output is correct
32 Correct 835 ms 13136 KB Output is correct
33 Correct 839 ms 13392 KB Output is correct
34 Correct 863 ms 13140 KB Output is correct
35 Correct 839 ms 13348 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 981 ms 49120 KB Output is correct
5 Correct 986 ms 60480 KB Output is correct
6 Correct 972 ms 60564 KB Output is correct
7 Correct 949 ms 62288 KB Output is correct
8 Correct 922 ms 62552 KB Output is correct
9 Correct 879 ms 62316 KB Output is correct
10 Correct 975 ms 60336 KB Output is correct
11 Correct 879 ms 58284 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12728 KB Output is correct
5 Correct 2 ms 12632 KB Output is correct
6 Correct 2 ms 12636 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Correct 2 ms 12680 KB Output is correct
9 Correct 2 ms 12636 KB Output is correct
10 Correct 2 ms 12636 KB Output is correct
11 Correct 2 ms 12636 KB Output is correct
12 Correct 1 ms 12636 KB Output is correct
13 Correct 2 ms 12636 KB Output is correct
14 Correct 2 ms 12636 KB Output is correct
15 Correct 2 ms 12888 KB Output is correct
16 Correct 2 ms 12636 KB Output is correct
17 Correct 2 ms 12636 KB Output is correct
18 Correct 2 ms 12632 KB Output is correct
19 Correct 2 ms 12636 KB Output is correct
20 Correct 143 ms 49632 KB Output is correct
21 Correct 150 ms 54872 KB Output is correct
22 Correct 161 ms 55304 KB Output is correct
23 Correct 146 ms 54736 KB Output is correct
24 Correct 151 ms 55120 KB Output is correct
25 Correct 157 ms 54956 KB Output is correct
26 Correct 144 ms 54864 KB Output is correct
27 Correct 146 ms 54776 KB Output is correct
28 Correct 153 ms 55136 KB Output is correct
29 Correct 149 ms 54868 KB Output is correct
30 Correct 145 ms 54864 KB Output is correct
31 Correct 149 ms 54864 KB Output is correct
32 Correct 149 ms 43088 KB Output is correct
33 Correct 159 ms 54636 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12728 KB Output is correct
5 Correct 2 ms 12632 KB Output is correct
6 Correct 2 ms 12636 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Correct 2 ms 12680 KB Output is correct
9 Correct 2 ms 12636 KB Output is correct
10 Correct 2 ms 12636 KB Output is correct
11 Correct 2 ms 12636 KB Output is correct
12 Correct 1 ms 12636 KB Output is correct
13 Correct 2 ms 12636 KB Output is correct
14 Correct 2 ms 12636 KB Output is correct
15 Correct 2 ms 12888 KB Output is correct
16 Correct 2 ms 12636 KB Output is correct
17 Correct 2 ms 12636 KB Output is correct
18 Correct 2 ms 12632 KB Output is correct
19 Correct 2 ms 12636 KB Output is correct
20 Correct 835 ms 13336 KB Output is correct
21 Correct 809 ms 13316 KB Output is correct
22 Correct 769 ms 13344 KB Output is correct
23 Correct 771 ms 13596 KB Output is correct
24 Correct 881 ms 13564 KB Output is correct
25 Correct 801 ms 13488 KB Output is correct
26 Correct 809 ms 13340 KB Output is correct
27 Correct 950 ms 13348 KB Output is correct
28 Correct 828 ms 13344 KB Output is correct
29 Correct 900 ms 13236 KB Output is correct
30 Correct 851 ms 13344 KB Output is correct
31 Correct 833 ms 13340 KB Output is correct
32 Correct 835 ms 13136 KB Output is correct
33 Correct 839 ms 13392 KB Output is correct
34 Correct 863 ms 13140 KB Output is correct
35 Correct 839 ms 13348 KB Output is correct
36 Correct 858 ms 13592 KB Output is correct
37 Correct 790 ms 14928 KB Output is correct
38 Correct 783 ms 15044 KB Output is correct
39 Correct 814 ms 14932 KB Output is correct
40 Correct 826 ms 14968 KB Output is correct
41 Correct 828 ms 15388 KB Output is correct
42 Correct 901 ms 15392 KB Output is correct
43 Correct 868 ms 15388 KB Output is correct
44 Correct 854 ms 15392 KB Output is correct
45 Correct 834 ms 15392 KB Output is correct
46 Correct 914 ms 15392 KB Output is correct
47 Correct 846 ms 15388 KB Output is correct
48 Correct 834 ms 15396 KB Output is correct
49 Correct 837 ms 15440 KB Output is correct
50 Correct 818 ms 15388 KB Output is correct
51 Correct 910 ms 15132 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12728 KB Output is correct
5 Correct 2 ms 12632 KB Output is correct
6 Correct 2 ms 12636 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Correct 2 ms 12680 KB Output is correct
9 Correct 2 ms 12636 KB Output is correct
10 Correct 2 ms 12636 KB Output is correct
11 Correct 2 ms 12636 KB Output is correct
12 Correct 1 ms 12636 KB Output is correct
13 Correct 2 ms 12636 KB Output is correct
14 Correct 2 ms 12636 KB Output is correct
15 Correct 2 ms 12888 KB Output is correct
16 Correct 2 ms 12636 KB Output is correct
17 Correct 2 ms 12636 KB Output is correct
18 Correct 2 ms 12632 KB Output is correct
19 Correct 2 ms 12636 KB Output is correct
20 Correct 835 ms 13336 KB Output is correct
21 Correct 809 ms 13316 KB Output is correct
22 Correct 769 ms 13344 KB Output is correct
23 Correct 771 ms 13596 KB Output is correct
24 Correct 881 ms 13564 KB Output is correct
25 Correct 801 ms 13488 KB Output is correct
26 Correct 809 ms 13340 KB Output is correct
27 Correct 950 ms 13348 KB Output is correct
28 Correct 828 ms 13344 KB Output is correct
29 Correct 900 ms 13236 KB Output is correct
30 Correct 851 ms 13344 KB Output is correct
31 Correct 833 ms 13340 KB Output is correct
32 Correct 835 ms 13136 KB Output is correct
33 Correct 839 ms 13392 KB Output is correct
34 Correct 863 ms 13140 KB Output is correct
35 Correct 839 ms 13348 KB Output is correct
36 Correct 2 ms 12632 KB Output is correct
37 Correct 2 ms 12636 KB Output is correct
38 Correct 2 ms 12636 KB Output is correct
39 Correct 981 ms 49120 KB Output is correct
40 Correct 986 ms 60480 KB Output is correct
41 Correct 972 ms 60564 KB Output is correct
42 Correct 949 ms 62288 KB Output is correct
43 Correct 922 ms 62552 KB Output is correct
44 Correct 879 ms 62316 KB Output is correct
45 Correct 975 ms 60336 KB Output is correct
46 Correct 879 ms 58284 KB Output is correct
47 Correct 2 ms 12636 KB Output is correct
48 Correct 143 ms 49632 KB Output is correct
49 Correct 150 ms 54872 KB Output is correct
50 Correct 161 ms 55304 KB Output is correct
51 Correct 146 ms 54736 KB Output is correct
52 Correct 151 ms 55120 KB Output is correct
53 Correct 157 ms 54956 KB Output is correct
54 Correct 144 ms 54864 KB Output is correct
55 Correct 146 ms 54776 KB Output is correct
56 Correct 153 ms 55136 KB Output is correct
57 Correct 149 ms 54868 KB Output is correct
58 Correct 145 ms 54864 KB Output is correct
59 Correct 149 ms 54864 KB Output is correct
60 Correct 149 ms 43088 KB Output is correct
61 Correct 159 ms 54636 KB Output is correct
62 Correct 858 ms 13592 KB Output is correct
63 Correct 790 ms 14928 KB Output is correct
64 Correct 783 ms 15044 KB Output is correct
65 Correct 814 ms 14932 KB Output is correct
66 Correct 826 ms 14968 KB Output is correct
67 Correct 828 ms 15388 KB Output is correct
68 Correct 901 ms 15392 KB Output is correct
69 Correct 868 ms 15388 KB Output is correct
70 Correct 854 ms 15392 KB Output is correct
71 Correct 834 ms 15392 KB Output is correct
72 Correct 914 ms 15392 KB Output is correct
73 Correct 846 ms 15388 KB Output is correct
74 Correct 834 ms 15396 KB Output is correct
75 Correct 837 ms 15440 KB Output is correct
76 Correct 818 ms 15388 KB Output is correct
77 Correct 910 ms 15132 KB Output is correct
78 Correct 1042 ms 59536 KB Output is correct
79 Correct 967 ms 61320 KB Output is correct
80 Correct 967 ms 60444 KB Output is correct
81 Correct 961 ms 60556 KB Output is correct
82 Correct 972 ms 59540 KB Output is correct
83 Correct 956 ms 59624 KB Output is correct
84 Correct 968 ms 59576 KB Output is correct
85 Correct 987 ms 59528 KB Output is correct
86 Correct 964 ms 59732 KB Output is correct
87 Correct 1004 ms 60820 KB Output is correct
88 Correct 974 ms 59520 KB Output is correct
89 Correct 976 ms 59588 KB Output is correct
90 Correct 962 ms 59636 KB Output is correct
91 Correct 999 ms 59208 KB Output is correct
92 Correct 947 ms 50068 KB Output is correct
93 Correct 983 ms 60404 KB Output is correct