Submission #568718

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
568718	2022-05-26T06:11:16 Z	maomao90	Reconstruction Project (JOI22_reconstruction)	C++17	31 / 100	5000 ms	38348 KB

reconstruction

// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h> 
using namespace std;

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define SZ(_a) (int) _a.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

const int INF = 1000000005;
const ll LINF = 1000000000000000005ll;
const int MAXM = 100005;
const int MAXN = 505;
const int MAXQ = 1000005;

int n, m;
iii edges[MAXM];
int q;
ii qry[MAXQ];
vii vw[MAXN];
int lft[MAXM], rht[MAXM];
ll ans[MAXQ];

int rp[MAXN], rnk[MAXN];
void init() {
    REP (i, 1, n + 1) {
        rnk[i] = 1;
        rp[i] = i;
    }
}
int findp(int i) {
    if (rp[i] == i) return i;
    return rp[i] = findp(rp[i]);
}
bool join(int a, int b) {
    int pa = findp(a), pb = findp(b);
    if (pa == pb) return 0;
    if (rnk[pa] < rnk[pb]) swap(pa, pb);
    if (rnk[pa] == rnk[pb]) rnk[pa]++;
    rp[pb] = pa;
    return 1;
}

bool isPos(int x, int id) {
    auto [ra, rb, rw] = edges[id];
    init();
    REP (i, 0, m) {
        if (i == id) {
            continue;
        }
        auto [a, b, w] = edges[i];
        if (ii{abs(w - x), i} < ii{abs(rw - x), id}) {
            join(a, b);
        }
    }
    return join(ra, rb);
}

int main() {
#ifndef DEBUG
    ios::sync_with_stdio(0), cin.tie(0);
#endif
    cin >> n >> m;
    REP (i, 0, m) {
        int a, b, w; cin >> a >> b >> w;
        edges[i] = {a, b, w};
    }
    cin >> q;
    REP (i, 0, q) {
        cin >> qry[i].FI;
        qry[i].SE = i;
    }
    viii ev;
    REP (i, 0, m) {
        auto [a, b, w] = edges[i];
        int lo = w - 1, hi = INF;
        while (lo < hi) {
            int mid = lo + hi + 1 >> 1;
            if (isPos(mid, i)) {
                lo = mid;
            } else {
                hi = mid - 1;
            }
        }
        rht[i] = lo + 1;
        lo = 0, hi = w + 1;
        while (lo < hi) {
            int mid = lo + hi >> 1;
            if (isPos(mid, i)) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        lft[i] = hi;
        cerr << i << ": " << lft[i] << ' ' << rht[i] << '\n';
        ev.pb({lft[i], w, 1});
        ev.pb({w + 1, -2 * w, -2});
        ev.pb({rht[i], w, 1});
    }
    sort(ALL(ev));
    int j = 0;
    ll res = 0;
    int minus = 0;
    REP (i, 0, q) {
        auto [x, id] = qry[i];
        while (j < SZ(ev) && get<0>(ev[j]) <= x) {
            auto [a, b, c] = ev[j];
            res += b;
            minus += c;
            j++;
        }
        ans[id] = res - (ll) x * minus;
    }
    REP (i, 0, q) {
        cout << ans[i] << '\n';
    }
    return 0;
}

Compilation message

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:102:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  102 |             int mid = lo + hi + 1 >> 1;
      |                       ~~~~~~~~^~~
reconstruction.cpp:112:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  112 |             int mid = lo + hi >> 1;
      |                       ~~~^~~~

Subtask #1

3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	352 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	264 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct

Subtask #2

0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	352 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	264 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Execution timed out	5065 ms	3196 KB	Time limit exceeded
21	Halted	0 ms	0 KB	-

Subtask #3

0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Execution timed out	5063 ms	9980 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #4

28.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	352 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	264 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	578 ms	37688 KB	Output is correct
21	Correct	556 ms	37836 KB	Output is correct
22	Correct	559 ms	38112 KB	Output is correct
23	Correct	571 ms	38064 KB	Output is correct
24	Correct	553 ms	38024 KB	Output is correct
25	Correct	560 ms	37988 KB	Output is correct
26	Correct	575 ms	37924 KB	Output is correct
27	Correct	583 ms	37956 KB	Output is correct
28	Correct	588 ms	37964 KB	Output is correct
29	Correct	601 ms	38016 KB	Output is correct
30	Correct	564 ms	37980 KB	Output is correct
31	Correct	532 ms	37880 KB	Output is correct
32	Correct	371 ms	38348 KB	Output is correct
33	Correct	537 ms	37872 KB	Output is correct

Subtask #5

0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	352 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	264 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Execution timed out	5065 ms	3196 KB	Time limit exceeded
21	Halted	0 ms	0 KB	-

Subtask #6

0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	352 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	264 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Execution timed out	5065 ms	3196 KB	Time limit exceeded
21	Halted	0 ms	0 KB	-