제출 #876775

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
876775		danikoynov	Reconstruction Project (JOI22_reconstruction)	C++14	100 / 100	2766 ms	451568 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)
{
    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];
vector < int > down_list[maxm], up_list[maxm];
void offline_mst()
{
    vector < int > new_list;
    for (int i = 1; i <= m; i ++)
    {
        for (int j = 1; j <= n; j ++)
            par[j] = j;
        new_list.clear();
        new_list.push_back(i);
        unite(edges[i].v, edges[i].u);
        for (int j = 0; j < down_list[i - 1].size(); j ++)
        {
            if (unite(edges[down_list[i - 1][j]].v, edges[down_list[i - 1][j]].u))
                new_list.push_back(down_list[i - 1][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;
        new_list.clear();
        new_list.push_back(i);
        unite(edges[i].v, edges[i].u);
        for (int j = 0; j < up_list[i + 1].size(); j ++)
        {
            if (unite(edges[up_list[i + 1][j]].v, edges[up_list[i + 1][j]].u))
                new_list.push_back(up_list[i + 1][j]);
        }
        up_list[i] = new_list;
        /**cout << "-----------" << endl;
        for (int cur : up_list[i])
            cout << cur << " ";
        cout << endl;*/
        ///assert(new_list.size() < n);
    }

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

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

        int left = edges[j].w, right = 1e9;
        if (d < up_list[j + 1].size())
        {
            int cur = up_list[j + 1][d];
            right = (edges[j].w + edges[cur].w) / 2;
            if ((edges[j].w + edges[cur].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 = 0;
        while(d < down_list[j - 1].size())
        {
            int cur = down_list[j - 1][d];
            unite(edges[cur].v, edges[cur].u);
            if (find_leader(edges[j].v) == find_leader(edges[j].u))
                break;
            d ++;
        }

        int right = edges[j].w, left = 0;
        if (d < down_list[j - 1].size())
        {
            int cur = down_list[j - 1][d];
            left = (edges[j].w + edges[cur].w) / 2;
            if ((edges[j].w + edges[cur].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;
}

컴파일 시 표준 에러 (stderr) 메시지

reconstruction.cpp: In function 'void offline_mst()':
reconstruction.cpp:91:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         for (int j = 0; j < down_list[i - 1].size(); j ++)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:108:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |         for (int j = 0; j < up_list[i + 1].size(); j ++)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:127:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |         while(d < up_list[j + 1].size())
      |               ~~^~~~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:137:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |         if (d < up_list[j + 1].size())
      |             ~~^~~~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:136:13: warning: unused variable 'left' [-Wunused-variable]
  136 |         int left = edges[j].w, right = 1e9;
      |             ^~~~
reconstruction.cpp:153:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |         while(d < down_list[j - 1].size())
      |               ~~^~~~~~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:163:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |         if (d < down_list[j - 1].size())
      |             ~~^~~~~~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:162:13: warning: unused variable 'right' [-Wunused-variable]
  162 |         int right = edges[j].w, left = 0;
      |             ^~~~~

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