oj.uz

Submission #876771

# Submission time Handle Problem Language Result Execution time Memory
876771 2023-11-22T10:10:20 Z danikoynov Reconstruction Project (JOI22_reconstruction) C++14
100 / 100
 1790 ms 66384 KB 
#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

const int maxn = 510, maxm = 1e5 + 10, maxq = 1e6 + 10;
const ll inf = 1e18;
struct edge
{
    int v, u;
    ll w;

    edge(int _v = 0, int _u = 0, ll _w = 0)
    {
        v = _v;
        u = _u;
        w = _w;
    }

    bool operator < (const edge &e) const
    {
        return w < e.w;
    }
}edges[maxm];

int n, m, q;
ll ans[maxq];

struct query
{
    int idx;
    ll x;

    bool operator < (const query &q1) const
    {
        return x < q1.x;
    }
}task[maxq];

void input()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i ++)
    {
        cin >> edges[i].v >> edges[i].u >> edges[i].w;
    }
    cin >> q;
    for (int i = 1; i <= q; i ++)
    {
        cin >> task[i].x;
        task[i].idx = i;
    }

    sort(edges + 1, edges + m + 1);
    sort(task + 1, task + q + 1);
}

int par[maxn];

int find_leader(int v)
{
    return (par[v] == v) ? v : (par[v] = find_leader(par[v]));
}

bool unite(int v, int u)
{
    v = find_leader(v);
    u = find_leader(u);
    if (v == u)
        return false;

    par[v] = u;

    return true;
}

int to_left[maxm], to_right[maxm];
ll to_add[maxq], cnt_add[maxq];

void offline_mst()
{
    for (int j = 1; j <= m; j ++)
    {
        for (int i = 1; i <= n; i ++)
            par[i] = i;

        int d = j + 1;
        while(d <= m)
        {
            unite(edges[d].v, edges[d].u);
            if (find_leader(edges[j].v) == find_leader(edges[j].u))
                break;
            d ++;
        }

        int left = edges[j].w, right = 1e9;
        if (d <= m)
        {
            right = (edges[j].w + edges[d].w) / 2;
            if ((edges[j].w + edges[d].w) % 2 == 0)
                right --;
        }
        to_right[j] = right;
    }

    for (int j = 1; j <= m; j ++)
    {
        for (int i = 1; i <= n; i ++)
            par[i] = i;

        int d = j - 1;
        while(d > 0)
        {
            unite(edges[d].v, edges[d].u);
            if (find_leader(edges[j].v) == find_leader(edges[j].u))
                break;
            d --;
        }

        int right = edges[j].w, left = 0;
        if (d > 0)
        {
            left = (edges[j].w + edges[d].w) / 2;
            if ((edges[j].w + edges[d].w) % 2 == 1)
                left ++;
        }

        to_left[j] = left;
    }

    for (int j = 1; j <= m; j ++)
    {
        int lf = 1, rf = q;
        while(lf <= rf)
        {
            int mf = (lf + rf) / 2;
            if (task[mf].x < to_left[j])
                lf = mf + 1;
            else
                rf = mf - 1;
        }

        int lb = lf;

        lf = 1;
        rf = q;
        while(lf <= rf)
        {
            int mf = (lf + rf) / 2;
            if (task[mf].x <= to_right[j])
                lf = mf + 1;
            else
                rf = mf - 1;
        }

        int rb = rf;

        if (lb > rb)
            continue;

        lf = 1;
        rf = q;
        while(lf <= rf)
        {
            int mf = (lf + rf) / 2;
            if (task[mf].x <= edges[j].w)
                lf = mf + 1;
            else
                rf = mf - 1;
        }

        int mb = lf - 1;

        to_add[lb] += edges[j].w;
        cnt_add[lb] ++;
        to_add[mb + 1] -= edges[j].w;
        to_add[mb + 1] -= edges[j].w;
        to_add[rb + 1] += edges[j].w;
        cnt_add[mb + 1] --;

        ///cout << j << " : " << to_left[j] << " " << to_right[j] << endl;
        //for (int i = 1; i <= q; i ++)
            //if (task[i].x >= to_left[j] && task[i].x <= to_right[j])
                //ans[task[i].idx] += abs(task[i].x - edges[j].w);
    }

    ll und = 0, sum = 0;
    for (int i = 1; i <= q; i ++)
    {
        und += cnt_add[i];
        sum += to_add[i];
        ans[task[i].idx] = sum - und * task[i].x + (n - 1 - und) * task[i].x;
    }

}
void answer()
{
    for (int i = 1; i <= q; i ++)
        cout << ans[i] << endl;
}

void solve()
{
    input();
    offline_mst();
    answer();
}

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int main()
{
    speed();
    solve();
    return 0;
}

Compilation message

reconstruction.cpp: In function 'void offline_mst()':
reconstruction.cpp:97:13: warning: unused variable 'left' [-Wunused-variable]
   97 |         int left = edges[j].w, right = 1e9;
      |             ^~~~
reconstruction.cpp:121:13: warning: unused variable 'right' [-Wunused-variable]
  121 |         int right = edges[j].w, left = 0;
      |             ^~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9048 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 1 ms 8856 KB Output is correct
5 Correct 1 ms 8796 KB Output is correct
6 Correct 1 ms 8796 KB Output is correct
7 Correct 1 ms 8796 KB Output is correct
8 Correct 1 ms 8932 KB Output is correct
9 Correct 1 ms 8796 KB Output is correct
10 Correct 1 ms 8796 KB Output is correct
11 Correct 2 ms 8796 KB Output is correct
12 Correct 1 ms 8796 KB Output is correct
13 Correct 1 ms 8796 KB Output is correct
14 Correct 1 ms 8796 KB Output is correct
15 Correct 1 ms 8840 KB Output is correct
16 Correct 1 ms 8780 KB Output is correct
17 Correct 1 ms 8796 KB Output is correct
18 Correct 2 ms 8796 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9048 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 1 ms 8856 KB Output is correct
5 Correct 1 ms 8796 KB Output is correct
6 Correct 1 ms 8796 KB Output is correct
7 Correct 1 ms 8796 KB Output is correct
8 Correct 1 ms 8932 KB Output is correct
9 Correct 1 ms 8796 KB Output is correct
10 Correct 1 ms 8796 KB Output is correct
11 Correct 2 ms 8796 KB Output is correct
12 Correct 1 ms 8796 KB Output is correct
13 Correct 1 ms 8796 KB Output is correct
14 Correct 1 ms 8796 KB Output is correct
15 Correct 1 ms 8840 KB Output is correct
16 Correct 1 ms 8780 KB Output is correct
17 Correct 1 ms 8796 KB Output is correct
18 Correct 2 ms 8796 KB Output is correct
19 Correct 2 ms 8796 KB Output is correct
20 Correct 1530 ms 8928 KB Output is correct
21 Correct 721 ms 8668 KB Output is correct
22 Correct 803 ms 8912 KB Output is correct
23 Correct 1024 ms 8912 KB Output is correct
24 Correct 1364 ms 8904 KB Output is correct
25 Correct 1611 ms 8912 KB Output is correct
26 Correct 1528 ms 8908 KB Output is correct
27 Correct 1526 ms 8904 KB Output is correct
28 Correct 1519 ms 8908 KB Output is correct
29 Correct 1510 ms 8908 KB Output is correct
30 Correct 1519 ms 8928 KB Output is correct
31 Correct 1527 ms 9164 KB Output is correct
32 Correct 1527 ms 9044 KB Output is correct
33 Correct 1519 ms 8912 KB Output is correct
34 Correct 1517 ms 8928 KB Output is correct
35 Correct 1525 ms 9040 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8796 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 871 ms 52980 KB Output is correct
5 Correct 880 ms 64368 KB Output is correct
6 Correct 873 ms 64520 KB Output is correct
7 Correct 620 ms 66380 KB Output is correct
8 Correct 545 ms 66160 KB Output is correct
9 Correct 469 ms 66384 KB Output is correct
10 Correct 860 ms 64220 KB Output is correct
11 Correct 507 ms 62116 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9048 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 1 ms 8856 KB Output is correct
5 Correct 1 ms 8796 KB Output is correct
6 Correct 1 ms 8796 KB Output is correct
7 Correct 1 ms 8796 KB Output is correct
8 Correct 1 ms 8932 KB Output is correct
9 Correct 1 ms 8796 KB Output is correct
10 Correct 1 ms 8796 KB Output is correct
11 Correct 2 ms 8796 KB Output is correct
12 Correct 1 ms 8796 KB Output is correct
13 Correct 1 ms 8796 KB Output is correct
14 Correct 1 ms 8796 KB Output is correct
15 Correct 1 ms 8840 KB Output is correct
16 Correct 1 ms 8780 KB Output is correct
17 Correct 1 ms 8796 KB Output is correct
18 Correct 2 ms 8796 KB Output is correct
19 Correct 1 ms 8796 KB Output is correct
20 Correct 176 ms 53992 KB Output is correct
21 Correct 169 ms 53996 KB Output is correct
22 Correct 186 ms 54100 KB Output is correct
23 Correct 167 ms 54000 KB Output is correct
24 Correct 166 ms 53980 KB Output is correct
25 Correct 175 ms 53896 KB Output is correct
26 Correct 168 ms 53996 KB Output is correct
27 Correct 175 ms 54248 KB Output is correct
28 Correct 166 ms 54004 KB Output is correct
29 Correct 166 ms 53928 KB Output is correct
30 Correct 170 ms 54096 KB Output is correct
31 Correct 166 ms 53844 KB Output is correct
32 Correct 168 ms 42316 KB Output is correct
33 Correct 168 ms 53736 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9048 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 1 ms 8856 KB Output is correct
5 Correct 1 ms 8796 KB Output is correct
6 Correct 1 ms 8796 KB Output is correct
7 Correct 1 ms 8796 KB Output is correct
8 Correct 1 ms 8932 KB Output is correct
9 Correct 1 ms 8796 KB Output is correct
10 Correct 1 ms 8796 KB Output is correct
11 Correct 2 ms 8796 KB Output is correct
12 Correct 1 ms 8796 KB Output is correct
13 Correct 1 ms 8796 KB Output is correct
14 Correct 1 ms 8796 KB Output is correct
15 Correct 1 ms 8840 KB Output is correct
16 Correct 1 ms 8780 KB Output is correct
17 Correct 1 ms 8796 KB Output is correct
18 Correct 2 ms 8796 KB Output is correct
19 Correct 2 ms 8796 KB Output is correct
20 Correct 1530 ms 8928 KB Output is correct
21 Correct 721 ms 8668 KB Output is correct
22 Correct 803 ms 8912 KB Output is correct
23 Correct 1024 ms 8912 KB Output is correct
24 Correct 1364 ms 8904 KB Output is correct
25 Correct 1611 ms 8912 KB Output is correct
26 Correct 1528 ms 8908 KB Output is correct
27 Correct 1526 ms 8904 KB Output is correct
28 Correct 1519 ms 8908 KB Output is correct
29 Correct 1510 ms 8908 KB Output is correct
30 Correct 1519 ms 8928 KB Output is correct
31 Correct 1527 ms 9164 KB Output is correct
32 Correct 1527 ms 9044 KB Output is correct
33 Correct 1519 ms 8912 KB Output is correct
34 Correct 1517 ms 8928 KB Output is correct
35 Correct 1525 ms 9040 KB Output is correct
36 Correct 1536 ms 11220 KB Output is correct
37 Correct 738 ms 11220 KB Output is correct
38 Correct 814 ms 11216 KB Output is correct
39 Correct 1032 ms 11348 KB Output is correct
40 Correct 1348 ms 11220 KB Output is correct
41 Correct 1622 ms 11232 KB Output is correct
42 Correct 1543 ms 11216 KB Output is correct
43 Correct 1544 ms 11220 KB Output is correct
44 Correct 1528 ms 11348 KB Output is correct
45 Correct 1520 ms 11220 KB Output is correct
46 Correct 1535 ms 11348 KB Output is correct
47 Correct 1533 ms 11224 KB Output is correct
48 Correct 1551 ms 11224 KB Output is correct
49 Correct 1530 ms 11452 KB Output is correct
50 Correct 1529 ms 11228 KB Output is correct
51 Correct 1524 ms 10964 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9048 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 1 ms 8856 KB Output is correct
5 Correct 1 ms 8796 KB Output is correct
6 Correct 1 ms 8796 KB Output is correct
7 Correct 1 ms 8796 KB Output is correct
8 Correct 1 ms 8932 KB Output is correct
9 Correct 1 ms 8796 KB Output is correct
10 Correct 1 ms 8796 KB Output is correct
11 Correct 2 ms 8796 KB Output is correct
12 Correct 1 ms 8796 KB Output is correct
13 Correct 1 ms 8796 KB Output is correct
14 Correct 1 ms 8796 KB Output is correct
15 Correct 1 ms 8840 KB Output is correct
16 Correct 1 ms 8780 KB Output is correct
17 Correct 1 ms 8796 KB Output is correct
18 Correct 2 ms 8796 KB Output is correct
19 Correct 2 ms 8796 KB Output is correct
20 Correct 1530 ms 8928 KB Output is correct
21 Correct 721 ms 8668 KB Output is correct
22 Correct 803 ms 8912 KB Output is correct
23 Correct 1024 ms 8912 KB Output is correct
24 Correct 1364 ms 8904 KB Output is correct
25 Correct 1611 ms 8912 KB Output is correct
26 Correct 1528 ms 8908 KB Output is correct
27 Correct 1526 ms 8904 KB Output is correct
28 Correct 1519 ms 8908 KB Output is correct
29 Correct 1510 ms 8908 KB Output is correct
30 Correct 1519 ms 8928 KB Output is correct
31 Correct 1527 ms 9164 KB Output is correct
32 Correct 1527 ms 9044 KB Output is correct
33 Correct 1519 ms 8912 KB Output is correct
34 Correct 1517 ms 8928 KB Output is correct
35 Correct 1525 ms 9040 KB Output is correct
36 Correct 1 ms 8796 KB Output is correct
37 Correct 1 ms 8796 KB Output is correct
38 Correct 1 ms 8796 KB Output is correct
39 Correct 871 ms 52980 KB Output is correct
40 Correct 880 ms 64368 KB Output is correct
41 Correct 873 ms 64520 KB Output is correct
42 Correct 620 ms 66380 KB Output is correct
43 Correct 545 ms 66160 KB Output is correct
44 Correct 469 ms 66384 KB Output is correct
45 Correct 860 ms 64220 KB Output is correct
46 Correct 507 ms 62116 KB Output is correct
47 Correct 1 ms 8796 KB Output is correct
48 Correct 176 ms 53992 KB Output is correct
49 Correct 169 ms 53996 KB Output is correct
50 Correct 186 ms 54100 KB Output is correct
51 Correct 167 ms 54000 KB Output is correct
52 Correct 166 ms 53980 KB Output is correct
53 Correct 175 ms 53896 KB Output is correct
54 Correct 168 ms 53996 KB Output is correct
55 Correct 175 ms 54248 KB Output is correct
56 Correct 166 ms 54004 KB Output is correct
57 Correct 166 ms 53928 KB Output is correct
58 Correct 170 ms 54096 KB Output is correct
59 Correct 166 ms 53844 KB Output is correct
60 Correct 168 ms 42316 KB Output is correct
61 Correct 168 ms 53736 KB Output is correct
62 Correct 1536 ms 11220 KB Output is correct
63 Correct 738 ms 11220 KB Output is correct
64 Correct 814 ms 11216 KB Output is correct
65 Correct 1032 ms 11348 KB Output is correct
66 Correct 1348 ms 11220 KB Output is correct
67 Correct 1622 ms 11232 KB Output is correct
68 Correct 1543 ms 11216 KB Output is correct
69 Correct 1544 ms 11220 KB Output is correct
70 Correct 1528 ms 11348 KB Output is correct
71 Correct 1520 ms 11220 KB Output is correct
72 Correct 1535 ms 11348 KB Output is correct
73 Correct 1533 ms 11224 KB Output is correct
74 Correct 1551 ms 11224 KB Output is correct
75 Correct 1530 ms 11452 KB Output is correct
76 Correct 1529 ms 11228 KB Output is correct
77 Correct 1524 ms 10964 KB Output is correct
78 Correct 1697 ms 63348 KB Output is correct
79 Correct 917 ms 65364 KB Output is correct
80 Correct 981 ms 64168 KB Output is correct
81 Correct 1177 ms 64336 KB Output is correct
82 Correct 1491 ms 63296 KB Output is correct
83 Correct 1790 ms 63384 KB Output is correct
84 Correct 1702 ms 63408 KB Output is correct
85 Correct 1695 ms 63312 KB Output is correct
86 Correct 1686 ms 63340 KB Output is correct
87 Correct 1666 ms 64592 KB Output is correct
88 Correct 1701 ms 63600 KB Output is correct
89 Correct 1707 ms 63288 KB Output is correct
90 Correct 1680 ms 63448 KB Output is correct
91 Correct 1692 ms 63232 KB Output is correct
92 Correct 1668 ms 53728 KB Output is correct
93 Correct 1694 ms 64156 KB Output is correct