Submission #877093

#	Time	Username	Problem	Language	Result	Execution time	Memory
877093		n3rm1n	Reconstruction Project (JOI22_reconstruction)	C++17	7 / 100	1332 ms	15784 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;
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 to_index[MAXN];
int main()
{
    speed();

    read_graph();

    cin >> q;
    if(q <= 10)solve_queries();
    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 = 1e9;
                if(j > 0)cost1 = qw - cost[i][j-1];
                long long cost2 = cost[i][j] - qw;
                ans += min(cost1, cost2);
            }
            cout << ans << endl;
        }
    }
    return 0;
}

Compilation message (stderr)

reconstruction.cpp: In function 'void solve_queries()':
reconstruction.cpp:90:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         while(j+1 < g.size() && g[j+1].w <= qw)
      |               ~~~~^~~~~~~~~~
reconstruction.cpp:94:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |         for (long long i = 0; i < g.size(); ++ i)
      |                               ~~^~~~~~~~~~
reconstruction.cpp:104: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]
  104 |         for (long long i = 0; i < edges.size() && used < n-1; ++ i)
      |                               ~~^~~~~~~~~~~~~~
reconstruction.cpp: In function 'int main()':
reconstruction.cpp:142:25: 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]
  142 |                 while(j < cost[i].size() && cost[i][j] <= qw)
      |                       ~~^~~~~~~~~~~~~~~~

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