Submission #1297152

#	Time	Username	Problem	Language	Result	Execution time	Memory
1297152		khoile08	Reconstruction Project (JOI22_reconstruction)	C++20	100 / 100	1179 ms	27224 KiB

reconstruction

#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FOD(i, a, b) for(int i = a; i >= b; i--)
#define int long long
#define fi first
#define se second
#define ll long long
#define db double 
#define pb push_back
#define ii pair<int,int>
#define sq(i) (1LL * (i) * (i))
#define MASK(i) (1LL << i)
#define task "task"

const int inf = 1e9;
const ll INF = 1e18;
const int N = 504;
const int M = 1e5 + 4;
const int Q = 1e6 + 4;

int n, m, q;
struct Edge {
    int u, v, w;
    bool operator < (const Edge &b) const {
        return w < b.w;
    }
} ed[M];
vector<Edge> ev;
int nxt[M];

vector<int> g[N];
int par[N], h[N];

struct Dsu {
    int root[N], sze[N];

    void init() {
        FOR(i, 1, n) {
            root[i] = i;
            sze[i] = 1;
        }
    }

    int anc(int u) {
        return root[u] == u ? u : root[u] = anc(root[u]);
    }

    bool join(int u, int v) {
        u = anc(u);
        v = anc(v);
        if(u == v) return false;
        root[v] = u;
        return true;
    }
} dsu;

void dfs(int u, int p) {
    par[u] = p;
    for(int id : g[u]) {
        if(id == p) continue;
        int v = u ^ ed[id].u ^ ed[id].v;
        h[v] = h[u] + 1;
        dfs(v, id);
    }
}

void buildtree() {
    FOR(i, 1, n) par[i] = h[i] = 0;
    FOR(i, 1, n) if(par[i] == 0) dfs(i, -1);
}

void Solve() {
    sort(ed + 1, ed + 1 + m);
    dsu.init();


    FOR(i, 1, m) {
        int u = ed[i].u, v = ed[i].v, w = ed[i].w;

        if(dsu.join(u, v)) {
            ev.pb({-1, w, 0});
            ev.pb({2, -2 * w, w});
        }
        else {
            int ru = u, rv = v, remove = -1;

            for(; ru != rv; ru = ru ^ ed[par[ru]].u ^ ed[par[ru]].v) {
                if(h[ru] < h[rv]) swap(ru, rv);
                int id = par[ru];
                if(remove == -1 || ed[remove].w > ed[id].w) remove = id;
            }

            g[ed[remove].u].erase(lower_bound(g[ed[remove].u].begin(), g[ed[remove].u].end(), remove));
            g[ed[remove].v].erase(lower_bound(g[ed[remove].v].begin(), g[ed[remove].v].end(), remove));
            nxt[remove] = i;
        }
        g[u].pb(i);
        g[v].pb(i);
        buildtree();
    }

    FOR(i, 1, m) {
        if(nxt[i] == 0) continue;
        int p = (ed[i].w + ed[nxt[i]].w + 1) / 2;
        ev.pb({-1, ed[i].w, p});
        ev.pb({-1, ed[nxt[i]].w, p});
        ev.pb({2, -2 * ed[nxt[i]].w, ed[nxt[i]].w});
    }

    sort(ev.begin(), ev.end());
    int p = 0;
    cin >> q;
    ii ans = {0, 0};
    FOR(i, 1, q) {
        int x; cin >> x;
        while(p < ev.size() && ev[p].w <= x) {
            ans.fi += ev[p].u;
            ans.se += ev[p].v;
            p++;
        }
        cout << ans.fi * x + ans.se << '\n';
    }
}

signed main() {
    if(fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        //freopen(task".out", "w", stdout); 
    }
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int tc = 1;
    // cin >> tc;
    while(tc--) {
        cin >> n >> m;
        FOR(i, 1, m) cin >> ed[i].u >> ed[i].v >> ed[i].w;
        Solve();
    }
}

Compilation message (stderr)

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:129:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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