Submission #906683

#	Time	Username	Problem	Language	Result	Execution time	Memory
906683		setytousi	Reconstruction Project (JOI22_reconstruction)	C++17	100 / 100	1886 ms	76300 KiB

reconstruction

#include<bits/stdc++.h>
using namespace std;
#define int ll
		 
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
		 
const ll MAXN = 1e6 + 6;
const ll MOD = 1e9 + 7;
const ll INF = 1e9 + 5;
const int s = 2048;

#define fast_io     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io     freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define pb          push_back
#define F           first
#define S           second
#define Sz(x)       int((x).size())
#define all(x)      (x).begin(), (x).end()
#define cl          clear()
#define endll       '\n'


int n, m, mn[MAXN], mx[MAXN], par[MAXN], cnt[MAXN];
ll ans[MAXN], out[MAXN];
vector<pair<int, pii>> edg;
vector<pii> query;

void init(){
    for (int i = 1; i <= n; i++) par[i] = i;
}
int root(int v){
    return (par[v] == v ? v : par[v] = root(par[v]));
}
void merge(int v, int u){
    v = root(v);
    u = root(u);
    if (v == u) return;
    par[v] = u;
}

int32_t main(){
    fast_io;
    cin >> n >> m;
    for (int i = 0; i < m; i++){
        int v, u, w;
        cin >> v >> u >> w; 
        if (v > u) swap(v, u);
        edg.pb({w, {v, u}});
    }
    fill(mx, mx + m, INF);
    fill(mn, mn + m, -INF);
    sort(all(edg));
    for (int i = 0; i < m; i++){
        init();
        for (int j = i - 1; j >= 0; j--){
            merge(edg[j].S.F, edg[j].S.S);
            if (root(edg[i].S.F) == root(edg[i].S.S)){
                mn[i] = (edg[i].F + edg[j].F) / 2 + ((edg[i].F + edg[j].F) % 2);
                break;
            }
        }
    }
    for (int i = 0; i < m; i++){
        init();
        for (int j = i + 1; j < m; j++){
            merge(edg[j].S.F, edg[j].S.S);
            if (root(edg[i].S.S) == root(edg[i].S.F)){
                mx[i] = (edg[i].F + edg[j].F) / 2 - ((edg[i].F + edg[j].F + 1) % 2) + 1;
                break;
            }
        }
    }
    int q;
    cin >> q;
    for (int i = 0; i < q; i++){
        int x;
        cin >> x;
        query.pb({x, i});
    }
    sort(all(query));
    for (int i = 0; i < m; i++){
        // cout << mn[i] << ' ' << mx[i] << endll;
        int val = edg[i].F;
        mn[i] = lower_bound(all(query), make_pair(mn[i], 0ll)) - query.begin();
        int mid = lower_bound(all(query), make_pair(val, 0ll)) - query.begin();
        mx[i] = lower_bound(all(query), make_pair(mx[i], 0ll)) - query.begin();
        ans[mn[i]] -= val;
        cnt[mn[i]]++;
        ans[mid] += 2 * val;
        cnt[mid]--;
        ans[mx[i]] -= val;
    }
    for (int i = 0; i < q; i++){
        if (i) ans[i] += ans[i - 1], cnt[i] += cnt[i - 1];
        out[query[i].S] = ans[i] + cnt[i] * query[i].F - (n - 1 - cnt[i]) * query[i].F;
    }
    for (int i = 0; i < q; i++) cout << -out[i] << endll;
}

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