Submission #876087

#	Time	Username	Problem	Language	Result	Execution time	Memory
876087		danikoynov	Reconstruction Project (JOI22_reconstruction)	C++14	42 / 100	5108 ms	807196 KiB

reconstruction

#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)
{
    if (v == par[v])
        return v;
    return (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;
}

vector < int > down_list[maxm], up_list[maxm];

void offline_mst()
{
    for (int i = 1; i <= m; i ++)
    {
        for (int j = 1; j <= n; j ++)
            par[j] = j;
        down_list[i] = down_list[i - 1];
        down_list[i].push_back(i);
        vector < int > new_list;
        for (int j = (int)(down_list[i].size()) - 1; j >= 0; j --)
        {
            if (unite(edges[down_list[i][j]].v, edges[down_list[i][j]].u))
                new_list.push_back(down_list[i][j]);
        }
        reverse(new_list.begin(), new_list.end());
        down_list[i] = new_list;
        assert(new_list.size() < n);
    }

    for (int i = m; i > 0; i --)
    {
        for (int j = 1; j <= n; j ++)
            par[j] = j;
        up_list[i] = up_list[i + 1];
        up_list[i].insert(up_list[i].begin(), i);
        vector < int > new_list;
        for (int j = 0; j < up_list[i].size(); j ++)
        {
            if (unite(edges[up_list[i][j]].v, edges[up_list[i][j]].u))
                new_list.push_back(up_list[i][j]);
        }
        up_list[i] = new_list;
        assert(new_list.size() < n);
    }
}
void answer()
{
    int pt = 1;
    for (int i = 1; i <= q; i ++)
    {
        while(pt <= m && edges[pt].w < task[i].x)
            pt ++;
        pt --;

        int lf = (int)(down_list[pt].size()) - 1, rf = 0;
        for (int j = 1; j <= n; j ++)
            par[j] = j;

        int cnt = 0;
        ll sum = 0;
        while(cnt < n - 1)
        {
            ll w_lf = inf, w_rf = inf;
            if (lf >= 0) w_lf = task[i].x - edges[down_list[pt][lf]].w;
            if (rf < up_list[pt + 1].size()) w_rf = edges[up_list[pt + 1][rf]].w - task[i].x;

            if (w_lf < w_rf)
            {
                bool tie = unite(edges[down_list[pt][lf]].v, edges[down_list[pt][lf]].u);
                if (tie)
                {
                    sum = sum + task[i].x - edges[down_list[pt][lf]].w;
                    cnt ++;
                }
                lf --;
            }
            else
            {
                bool tie = unite(edges[up_list[pt + 1][rf]].v, edges[up_list[pt + 1][rf]].u);
                if (tie)
                {
                    sum = sum + edges[up_list[pt + 1][rf]].w - task[i].x;
                    cnt ++;
                }
                rf ++;
            }
        }

        ans[task[i].idx] = sum;
    }

    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 (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from reconstruction.cpp:1:
reconstruction.cpp: In function 'void offline_mst()':
reconstruction.cpp:97:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   97 |         assert(new_list.size() < n);
      |                ~~~~~~~~~~~~~~~~^~~
reconstruction.cpp:107:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |         for (int j = 0; j < up_list[i].size(); j ++)
      |                         ~~^~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from reconstruction.cpp:1:
reconstruction.cpp:113:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  113 |         assert(new_list.size() < n);
      |                ~~~~~~~~~~~~~~~~^~~
reconstruction.cpp: In function 'void answer()':
reconstruction.cpp:135:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |             if (rf < up_list[pt + 1].size()) w_rf = edges[up_list[pt + 1][rf]].w - task[i].x;
      |                 ~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 0 / 7
• Subtask 4: 0 / 28
• Subtask 5: 35 / 35
• Subtask 6: 0 / 23