Submission #877552

#	Time	Username	Problem	Language	Result	Execution time	Memory
877552		n3rm1n	Reconstruction Project (JOI22_reconstruction)	C++17	42 / 100	5110 ms	796840 KiB

reconstruction

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const long long MAXN = 1e5 + 10;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
long long n, m;
struct edge
{
    long long index, from, to, w;
    edge() {};
    edge(long long _index, long long _from, long long _to, long long _w)
    {
        index = _index;
        from = _from;
        to = _to;
        w = _w;
    }
};
bool cmp(edge e1, edge e2)
{
    if(e1.w != e2.w)return (e1.w < e2.w);
    return (e1.from < e2.from);
}
vector < edge > g;
vector < long long > cost[MAXN];
long long group3 = 1;
void read_graph()
{
    cin >> n >> m;
    long long xx, yy, ww;
    for (long long i = 1; i <= m; ++ i)
    {
        cin >> xx >> yy >> ww;
        if(yy != xx+1)group3 = 0;
        cost[xx].push_back(ww);
        g.push_back(edge(i, xx, yy, ww));
    }
    sort(g.begin(), g.end(), cmp);
    for (long long i = 1; i < n; ++ i)
        sort(cost[i].begin(), cost[i].end());

}

long long p[MAXN], r[MAXN];

void init()
{
    for (long long i = 1; i <= n; ++ i)
    {
        p[i] = i;
        r[i] = 1;
    }
}

long long find_leader(long long i)
{
    if(p[i] == i)return i;
    else return find_leader(p[i]);
}

bool connected(long long i, long long j)
{
    return (find_leader(i) == find_leader(j));
}

void dsu(long long i, long long j)
{
    i = find_leader(i);
    j = find_leader(j);
    if(i == j)return;
    if(r[i] < r[j])swap(i, j);
    p[j] = p[i];
    r[i] += r[j];
}
/*
long long q;
void solve_queries()
{

    long long j = -1;
    long long qw;
    vector < pair <long long, long long > > edges;
    while(q --)
    {
        cin >> qw;
        while(j+1 < g.size() && g[j+1].w <= qw)
            j ++;

        edges.clear();
        for (long long i = 0; i < g.size(); ++ i)
        {
            if(i <= j)edges.push_back(make_pair(qw - g[i].w, (i+1)));
            else edges.push_back(make_pair(g[i].w - qw, -i-1));
        }
        sort(edges.begin(), edges.end());
        init();

        long long best = 0, used = 0;
        long long from, to;
        for (long long i = 0; i < edges.size() && used < n-1; ++ i)
        {

            from = g[abs(edges[i].second)-1].from;
            to = g[abs(edges[i].second)-1].to;
            if(!connected(from, to))
            {
                used ++;
                dsu(from, to);
                best += edges[i].first;
            }
        }
        cout << best << endl;

    }
    exit(0);
}*/
long long q;
vector < long long > indexes_used_left[MAXN], indexes_used_right[MAXN];
void precompute()
{
    init();
    long long used = 0;
    vector < long long > curr_used;
    long long last_used = 0;
    long long from, to;

    for (long long i = 0; i < g.size(); ++ i)
    {
        init();
        curr_used.clear();
        used = 0;

        from = g[i].from;
        to = g[i].to;
        if(!connected(from, to))
        {
            used ++;
            dsu(from, to);
            curr_used.push_back(i);
        }
        for (long long j = indexes_used_left[i-1].size()-1; j >= 0 && used < n; -- j)
        {
            from = g[indexes_used_left[i-1][j]].from;
            to = g[indexes_used_left[i-1][j]].to;
            if(!connected(from, to))
            {
                used ++;
                dsu(from, to);
                curr_used.push_back(indexes_used_left[i-1][j]);
            }
        }
        reverse(curr_used.begin(), curr_used.end());
        indexes_used_left[i] = curr_used;


    }
    for (long long i = g.size()-1; i >= 0; -- i)
    {
        init();
        curr_used.clear();
        used = 0;

        from = g[i].from;
        to = g[i].to;
        if(!connected(from, to))
        {
            used ++;
            dsu(from, to);
            curr_used.push_back(i);
        }
        for (long long j = 0; j < indexes_used_right[i+1].size() && used < n; ++ j)
        {
            from = g[indexes_used_right[i+1][j]].from;
            to = g[indexes_used_right[i+1][j]].to;
            if(!connected(from, to))
            {
                used ++;
                dsu(from, to);
                curr_used.push_back(indexes_used_right[i+1][j]);
            }
        }

        indexes_used_right[i] = curr_used;


    }
}
void solve_queries()
{
    long long qw;
    long long i = 0;
    while(q --)
    {
        cin >> qw;
        while(i < g.size() && g[i].w <= qw)
            i ++;
        vector < pair < long long, long long > > edges;
        if(i-1 >= 0)
        {
            for (long long j = 0; j < indexes_used_left[i-1].size(); ++ j)
            {
                long long index = indexes_used_left[i-1][j];
                long long ww = g[index].w;
                edges.push_back(make_pair(abs(ww - qw), index));
            }
        }
        if(i < g.size())
        {
            for (long long j = 0; j < indexes_used_right[i].size(); ++ j)
            {
                long long index = indexes_used_right[i][j];
                long long ww = g[index].w;
                edges.push_back(make_pair(abs(ww - qw), index));
            }
        }
        sort(edges.begin(), edges.end());
        init();
        long long best = 0, used = 0;
        long long from, to;
        for (long long i = 0; i < edges.size() && used < n-1; ++ i)
        {

            from = g[edges[i].second].from;
            to = g[edges[i].second].to;
            if(!connected(from, to))
            {
                used ++;
                dsu(from, to);
                best += edges[i].first;
            }
        }
        cout << best << endl;
    }
}
int main()
{
    speed();

    read_graph();

    cin >> q;
    /*if(group3)
    {

        long long qw;
        while(q --)
        {
            cin >> qw;
            long long ans = 0;

            for (long long i = 1; i < n; ++ i)
            {
                long long j = to_index[i];
                while(j < cost[i].size() && cost[i][j] <= qw)
                    j ++;
                to_index[i] = j;
                long long cost1 = 1LL * 1e9;
                if(j > 0)cost1 = qw - cost[i][j-1];
                long long cost2 = 1LL * 1e9;
                if(j < cost[i].size())cost2 = cost[i][j] - qw;
                ans += 1LL * min(cost1, cost2);
            }
            cout << ans << endl;
        }
        exit(0);
    }
    if(q <= 10)
    {
        solve_queries();
        exit(0);
    }*/
    precompute();
    solve_queries();
    return 0;
}
/***
3 4
1 2 16778865
1 2 17655676
2 3 56475445
2 3 77565565
4
23445345
27675656
67868767

77565565
*/

Compilation message (stderr)

reconstruction.cpp: In function 'void precompute()':
reconstruction.cpp:132:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |     for (long long i = 0; i < g.size(); ++ i)
      |                           ~~^~~~~~~~~~
reconstruction.cpp:176:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  176 |         for (long long j = 0; j < indexes_used_right[i+1].size() && used < n; ++ j)
      |                               ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:129:15: warning: unused variable 'last_used' [-Wunused-variable]
  129 |     long long last_used = 0;
      |               ^~~~~~~~~
reconstruction.cpp: In function 'void solve_queries()':
reconstruction.cpp:200:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  200 |         while(i < g.size() && g[i].w <= qw)
      |               ~~^~~~~~~~~~
reconstruction.cpp:205:37: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  205 |             for (long long j = 0; j < indexes_used_left[i-1].size(); ++ j)
      |                                   ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:212:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  212 |         if(i < g.size())
      |            ~~^~~~~~~~~~
reconstruction.cpp:214:37: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  214 |             for (long long j = 0; j < indexes_used_right[i].size(); ++ j)
      |                                   ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:225:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  225 |         for (long long i = 0; i < edges.size() && used < n-1; ++ i)
      |                               ~~^~~~~~~~~~~~~~

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