Submission #1060938

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060938		sleepntsheep	Reconstruction Project (JOI22_reconstruction)	C++17	7 / 100	5086 ms	11324 KiB

reconstruction

#pragma GCC optimize("O3,unroll-loops")
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <array>

using namespace std;
using ll = long long;

template <typename T, int sz>
using ar = array<T, sz>;

const int N = 505, M = 101000;

int n, m, q, ds[N];
ll mst;

ar<int, 3> e[M];

int ds_find(int i) {
    return (ds[i] < 0) ? i : (ds[i] = ds_find(ds[i]));
}

void ds_unite(int i, int j, int w) {
    i = ds_find(i);
    j = ds_find(j);
    if (i == j) return;
    mst += w;
    if (-ds[i] > -ds[j]) swap(i, j);
    ds[j] += ds[i];
    ds[i] = j;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++i)
        scanf("%d%d%d", &e[i][1], &e[i][2], &e[i][0]);
    sort(e, e+m);
    scanf("%d", &q);
    int k = 0;
    for (int x, i = 0; i < q; ++i) {
        scanf("%d", &x);

        memset(ds, -1, sizeof * ds * (n + 1));
        mst = 0;

        while (k < m && e[k][0] < x) ++k;
        int pl, pr;
        pr = k;
        pl = pr - 1;

        while (pl >= 0 or pr < m)
            if (pl == -1 or pr < m and e[pr][0] - x < x - e[pl][0])
                ds_unite(e[pr][1], e[pr][2], e[pr][0] - x), ++pr;
            else
                ds_unite(e[pl][1], e[pl][2], x - e[pl][0]), --pl;

        printf("%lld\n", mst);
    }

}

Compilation message (stderr)

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:54:36: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   54 |             if (pl == -1 or pr < m and e[pr][0] - x < x - e[pl][0])
reconstruction.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
reconstruction.cpp:38:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         scanf("%d%d%d", &e[i][1], &e[i][2], &e[i][0]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
reconstruction.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         scanf("%d", &x);
      |         ~~~~~^~~~~~~~~~

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