Submission #877530

#	Time	Username	Problem	Language	Result	Execution time	Memory
877530		Ice_man	Reconstruction Project (JOI22_reconstruction)	C++14	100 / 100	4058 ms	50880 KiB

reconstruction

#include <iostream>
#include <vector>
#include <algorithm>

#define INF 1000000005
#define LINF 1000000000000000005
#define pb(x) push_back(x)
#define maxn 505
#define maxm 100005
#define maxq 1000005
#define control cout<<"passed"<<endl;

#pragma GCC optimize("O3" , "Ofast" , "unroll-loops")
#pragma GCC target(avx2)

using namespace std;

struct edge1
{
    long long to , val;
    edge1(){};
    edge1(long long to2 , long long val2)
    {
        to = to2;
        val = val2;
    }
};

struct edge2
{
    long long from , to , val;
    edge2(){};
    edge2(long long from2 , long long to2 , long long val2)
    {
        from = from2;
        to = to2;
        val = val2;
    }
};


long long n , m;

vector <edge1> v[maxn];
edge2 edges[maxm];

vector <long long> queries;
long long q;

void read()
{
    cin >> n >> m;

    long long from , to , val;

    ///edges.resize(m + 1);
    for(long long i = 1; i <= m; i++)
    {
        cin >> edges[i].from >> edges[i].to >> edges[i].val;

        v[from].push_back({to , val});
        v[to].push_back({from , val});

        ///edges.push_back({from , to , val});

    }

    ///control

    cin >> q;
    queries.resize(q + 1);

    for(long long i = 1; i <= q; i++) cin >> queries[i];;


}

long long parent[maxn];

long long find_parent(long long node)
{
    return node == parent[node]? node :  parent[node] = find_parent(parent[node]);
}

long long d[maxn];

bool unite(long long a , long long b)
{
    a = find_parent(a);
    b = find_parent(b);

    if(a == b) return false;

    if(d[a] < d[b]) swap(a , b);

    parent[b] = a;
    d[a] += d[b];

    return true;

}

bool cmp(edge2 e1 , edge2 e2)
{
    return e1.val < e2.val;
}

long long low[maxm] , high[maxm];

vector <edge2> help;

bool cmp2(edge2 e1 , edge2 e2)
{
    return e1.from < e2.from;
}


void solve()
{

    sort(edges + 1 , edges + 1 + m , cmp);

    ///control

    for(long long i = 1; i <= m; i++)
    {
        low[i] = -INF;
        high[i] = INF;
    }

    long long p1 , p2;

    for(long long i = 1; i <= m; i++)
    {
        ///control

        for(long long i = 1; i <= n; i++) parent[i] = i;

        p1 = i - 1;

        while(p1 >= 1 && find_parent(edges[i].from) != find_parent(edges[i].to))
        {

            //if(p1 < 1) break;

            unite(edges[p1].from , edges[p1].to);
            p1--;

        }

        if(find_parent(edges[i].from) == find_parent(edges[i].to)) p1++;

        for(long long i = 1; i <= n; i++) parent[i] = i;

        p2 = i + 1;

        while(p2 <= m && find_parent(edges[i].from) != find_parent(edges[i].to))
        {
            //if(p2 > m) break;

            unite(edges[p2].from , edges[p2].to);

            p2++;

        }

        if(find_parent(edges[i].from) == find_parent(edges[i].to)) p2--;

        if(p1 >= 1) low[i] = (edges[p1].val + edges[i].val + 1) / 2;
        if(p2 <= m) high[i] = (edges[p2].val + edges[i].val - 1) / 2;


        help.push_back({low[i] , 1 , -edges[i].val});
        help.push_back({edges[i].val , -2 , 2 * edges[i].val});
        help.push_back({high[i] + 1 , 1 , -edges[i].val});


    }

    ///control

    sort(help.begin() , help.end() , cmp2);

    long long a;
    long long b;

    a = b = 0;
    long long _pointer = 0;

    for(long long i = 1; i < queries.size(); i++)
    {
        while(_pointer < help.size() && help[_pointer].from <= queries[i])
        {
            a += help[_pointer].to;
            b += help[_pointer].val;

            _pointer++;

        }

        ///cout << a << " " << b << endl;

        long long ans = (a * queries[i] + b);
        ans = -ans;

        cout << ans << endl;

    }


}

int main()
{
    /**ios_base::sync_with_stdio(false);
    cin.tie(nullptr);*/

    read();
    solve();

    return 0;
}

Compilation message (stderr)

reconstruction.cpp:14:20: warning: '#pragma GCC option' is not a string [-Wpragmas]
   14 | #pragma GCC target(avx2)
      |                    ^~~~
reconstruction.cpp: In function 'void solve()':
reconstruction.cpp:190:28: 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]
  190 |     for(long long i = 1; i < queries.size(); i++)
      |                          ~~^~~~~~~~~~~~~~~~
reconstruction.cpp:192:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<edge2>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  192 |         while(_pointer < help.size() && help[_pointer].from <= queries[i])
      |               ~~~~~~~~~^~~~~~~~~~~~~
reconstruction.cpp: In function 'void read()':
reconstruction.cpp:54:15: warning: 'from' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |     long long from , to , val;
      |               ^~~~
reconstruction.cpp:54:22: warning: 'to' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |     long long from , to , val;
      |                      ^~
reconstruction.cpp:54:27: warning: 'val' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |     long long from , to , val;
      |                           ^~~

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