Submission #770979

#	Time	Username	Problem	Language	Result	Execution time	Memory
770979		vjudge1	다리 (APIO19_bridges)	C++17	14 / 100	1543 ms	10600 KiB

bridges

// #cheat_when_I_was_young
// #cheatkhitacontre #khionhatoicheat
// #thaycuckythatvong
#include "bits/stdc++.h"
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
const int NM = 5e4 + 5, MN = 1e5 + 5, block1 = 800;
const int block2 = MN / block1 + 5;
int par[NM], sz[NM];
stack<tuple<int,int,int,int>> st;
int find_set(int u) {
    return par[u] == u ? u : find_set(par[u]);
}
void union_set(int u, int v, bool save) {
    u = find_set(u);
    v = find_set(v);
    if (u == v) return;
    if (sz[u] < sz[v]) swap(u, v);
    if (save) st.push({u, sz[u], v, par[v]});
    par[v] = u;
    sz[u] += sz[v];
}
void rollback() {
    while (!st.empty()) {
        sz[get<0>(st.top())] = get<1>(st.top());
        par[get<2>(st.top())] = get<3>(st.top());
        st.pop();
    }
}
int nEdge = 1;
struct edge {
    int u, v, w, id;
    friend istream & operator >> (istream &in, edge &A) {
        in >> A.u >> A.v >> A.w;
        A.id = nEdge++;
        return in;
    }
    bool operator < (edge &A) {
        return w > A.w;
    }
};
int nQuery = 1;
struct query {
    int type, u, w, id;
    friend istream & operator >> (istream &in, query &A) {
        in >> A.type >> A.u >> A.w;
        A.id = nQuery++;
        return in;
    }
    bool operator < (query &A) {
        return w > A.w;
    }
};
int n, m, q, ans[MN], ptr;
edge a[MN], aa[MN];
vector<query> b[block2], t[3];
bool change[MN], chosed[MN];
void solve_query(query &A) {
    for (; ptr <= m; ++ptr) {
        if (change[aa[ptr].id]) continue;
        if (aa[ptr].w >= A.w) {
            union_set(aa[ptr].u, aa[ptr].v, 0);
        } else break;
    }
    for (auto &B: t[1]) {
        if (B.id > A.id) continue;
        if (chosed[B.u]) continue;
        chosed[B.u] = 1;
        if (B.w >= A.w) union_set(a[B.u].u, a[B.u].v, 1);
    }
    ans[A.id] = sz[find_set(A.u)];
    for (auto &B: t[1]) chosed[B.u] = 0;
    rollback();
}
void solve(vector<query> &c) {
    if (!c.size()) return;
    for (int i = 1; i <= m; ++i) aa[i] = a[i];
    sort(aa+1, aa+m+1);
    t[1].clear();
    t[2].clear();
    memset(change, 0, sizeof(change));
    for (auto &A: c) {
        t[A.type].push_back(A);
        if (A.type == 1) change[A.u] = 1;
    }
    reverse(t[1].begin(), t[1].end());
    for (int i = 1; i <= m; ++i) if (change[i]) t[1].push_back({1, i, a[i].w, 0});
    sort(t[2].begin(), t[2].end());
    ptr = 1;
    for (int i = 1; i <= n; ++i) {
        par[i] = i;
        sz[i] = 1;
    }
    for (auto &A: t[2]) solve_query(A);
    for (auto &A: t[1]) {
        if (!A.id) break;
        a[A.u].w = A.w;
    }
}
signed main() {
	IOS;
	cin >> n >> m;
    for (int i = 1; i <= m; ++i) cin >> a[i];
    cin >> q;
    for (int i = 1; i <= q; ++i) {
        query tmp;
        cin >> tmp;
        b[i/block1].push_back(tmp);
    }
    for (int i = 0; i < block2; ++i) solve(b[i]);
    for (int i = 1; i <= q; ++i) if (ans[i]) cout << ans[i] << "\n";
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 14 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27