Submission #416374

#	Time	Username	Problem	Language	Result	Execution time	Memory
416374		model_code	Rooted MST (innopolis2021_final_E)	C++17	100 / 100	1313 ms	100572 KiB

Main

#include <bits/stdc++.h>
#define ws weights

using namespace std;

typedef long long ll;


const int N = 3e5 + 10;
const int inf = 1e9 + 20;
const ll infty = (ll) (1e18);

int dsu[N];
vector <int> vs[N], ws[N];

int get(int v) {
    if (v == dsu[v]) return v;
    else return dsu[v] = get(dsu[v]);
}

void uni(int u, int v, int w) {
    u = get(u), v = get(v);
    if (vs[u].size() > vs[v].size()) swap(u, v);
    for (int x : vs[u]) vs[v].push_back(x);
    ws[v].push_back(w);
    for (int x : ws[u]) ws[v].push_back(x);
    dsu[u] = v;
}

int cost[N];
int edge_r[N];
ll t[4 * N][2][2];

void recalc(int v, int l, int r) {
    int m = (l + r) / 2;
    int my_w = edge_r[m - 1];
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            t[v][i][j] = t[v * 2 + 1][i][1] + t[v * 2 + 2][1][j];
        }
    }
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            int k = 1 ^ j;
            for (int l = 0; l < 2; l++) {
                t[v][i][l] = min(t[v][i][l], t[v * 2 + 1][i][j] + t[v * 2 + 2][k][l] + my_w);
            }
        }
    }
}

void build_leaf(int v, int i) {
    for (int x = 0; x < 2; x++) {
        for (int y = 0; y < 2; y++) {
            t[v][x][y] = (x && y ? cost[i] : 0);
        }
    }
}

void build(int v, int l, int r) {
    if (r - l == 1) {
        build_leaf(v, l);
    } else {
        int m = (l + r) / 2;
        build(v * 2 + 1, l, m);
        build(v * 2 + 2, m, r);
        recalc(v, l, r);
    }
}

void upd(int v, int l, int r, int i) {
    if (r - l == 1) {
        build_leaf(v, l);
    } else {
        int m = (l + r) / 2;
        if (i < m) {
            upd(v * 2 + 1, l, m, i);
        } else {
            upd(v * 2 + 2, m, r, i);
        }
        recalc(v, l, r);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector <int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    vector <pair <int, pair <int, int> > > e;
    auto add_edge = [&] (int a, int b, int w) {
        e.push_back({w, {a, b}});
    };
    for (int i = 2; i <= n; i++) {
        add_edge(i, i - 1, inf);
    }
    for (int i = 0; i < m; i++) {
        int w, u, v;
        cin >> u >> v >> w;
        add_edge(u, v, w);
    }
    sort(e.begin(), e.end());
    for (int i = 1; i <= n; i++) {
        dsu[i] = i;
        vs[i] = {i};
        ws[i] = {};
    }
    for (auto c : e) {
        int u = c.second.first, v = c.second.second;
        if (get(u) != get(v)) {
            uni(u, v, c.first);
        }
    }
    vector <int> perm(n + 1);
    int root = get(1);
    for (int i = 0; i < (int) vs[root].size(); i++) {
        perm[vs[root][i]] = i;
        if (i + 1 < (int) vs[root].size())
            edge_r[i] = ws[root][i];
    }
    for (int i = 1; i <= n; i++) {
        cost[perm[i]] = a[i];
    }
    build(0, 0, n);
    int q;
    cin >> q;
    while (q--) {
        int i, w;
        cin >> i >> w;
        i = perm[i];
        cost[i] = w;
        upd(0, 0, n, i);
        cout << t[0][1][1] << '\n';
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 20 / 20
• Subtask 8: 20 / 20