Submission #877066

#	Time	Username	Problem	Language	Result	Execution time	Memory
877066		n3rm1n	Reconstruction Project (JOI22_reconstruction)	C++17	7 / 100	5076 ms	9668 KiB

reconstruction

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const long long MAXN = 505;
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;
void read_graph()
{
    cin >> n >> m;
    long long xx, yy, ww;
    for (long long i = 1; i <= m; ++ i)
    {
        cin >> xx >> yy >> ww;
        g.push_back(edge(i, xx, yy, ww));
    }
    sort(g.begin(), g.end(), cmp);


}
/**/////////////////////////////
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];
}
/**/
void solve_queries()
{
    long long q;
    cin >> q;
    long long shift = 0;
    long long went = 0;
    long long j = -1;
    long long qw;
    long long best = 1e9;
    long long last = 0;
    vector < pair <long long, long long > > edges;
    while(q --)
    {
        cin >> qw;

        went ++;
        shift = 0;
        while(j+1 < g.size() && g[j+1].w <= qw)
        {
            j ++;
            shift ++;
        }

        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 curr_best = 0, used = 0;
        for (long long i = 0; i < edges.size() && used < n-1; ++ i)
        {

            long long from = g[abs(edges[i].second)-1].from;
            long long to = g[abs(edges[i].second)-1].to;
            ///cout << from << " " << to << " " << edges[i].first << endl;
            if(!connected(from, to))
            {

                used ++;
                dsu(from, to);
                curr_best += edges[i].first;
            }
        }
        best = curr_best;
        cout << best << endl;
        last = qw;

    }
}
int main()
{
    speed();

    read_graph();
    solve_queries();
    return 0;
}

Compilation message (stderr)

reconstruction.cpp: In function 'void solve_queries()':
reconstruction.cpp:93:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |         while(j+1 < g.size() && g[j+1].w <= qw)
      |               ~~~~^~~~~~~~~~
reconstruction.cpp:100:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |         for (long long i = 0; i < g.size(); ++ i)
      |                               ~~^~~~~~~~~~
reconstruction.cpp:112: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]
  112 |         for (long long i = 0; i < edges.size() && used < n-1; ++ i)
      |                               ~~^~~~~~~~~~~~~~
reconstruction.cpp:85:15: warning: variable 'last' set but not used [-Wunused-but-set-variable]
   85 |     long long last = 0;
      |               ^~~~

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